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.
parameterized complexity cluster editing correlation clustering subexponential-time algorithms exponential-time hypothesis