Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

• The problem is to partition a graph into cliques by editing a small number of edges.
• We study the problem from the perspective of parameterized complexity.
• We give a parameterized algorithm.
• The running time is subexponential if the target number of clusters is sublinear.
• We show that the running time of our algorithm is tight assuming ETH.

In the Cluster Editing problem, also known as Correlation Clustering, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k   edges. We give a subexponential-time parameterized algorithm that in time 2O(pk)+nO(1) decides whether G can be transformed into a cluster graph with exactly p cliques by changing at most k   adjacencies. Our algorithmic findings are complemented by the following tight lower bound on the asymptotic behavior of our algorithm. We show that unless ETH fails, for any constant 0<σ≤10<σ≤1, there is p=Θ(kσ)p=Θ(kσ) such that there is no algorithm deciding in time 2o(pk)⋅nO(1) whether G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies.