γ-clustering problems: Classical and parametrized complexity.

We introduce the γ -clustering problems, which are variants of the well-known Cluster Editing/Deletion/Completion problems, and defined as: given a graph G , how many edges must be edited in G , deleted from G , or added to G in order to have a disjoint union of γ -quasi-cliques. We provide here the complete complexity classification of these problems along with FPT algorithms parameterized by the number of modifications, for the NP -complete problems. We also study here a variant of these problems where the number of final clusters is a fixed constant, obtaining mostly the same results regarding classical and parameterized complexity. [ABSTRACT FROM AUTHOR]