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.