Graph clustering problems under the lens of parameterized local search

Cluster Editing is the problem of finding the minimum number of edge-modifications that transform a given graph G into a cluster graph G , that is, each connected component of G is a clique. Similarly, in the CLUSTER DELETION problem, we further restrict the sought cluster graph G to contain only edges that are also present in G. In this work, we consider the parameterized complexity of a local search variant for both problems: LS CLUSTER DELETION and LS CLUSTER EDITING. Herein, the input also comprises an integer k and a partition of the vertex set of G that describes an initial cluster graph G* , and we are to decide whether the "k-move-neighborhood" of G* contains a cluster graph G that is "better" (uses less modifications) than G* . Roughly speaking, two cluster graphs G1 and G2 are k-move-neighbors if G1 can be obtained from G2 by moving at most k vertices to different connected components. We consider parameterizations by k + ℓ for some natural parameters ℓ, such as the number of clusters in , the size of a largest cluster in , or the cluster-vertex-deletion number (cvd) of G.