Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters
作者：
Highlights：
• 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.
摘要
•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.
论文关键词：Cluster editing,Correlation clustering,Parameterized complexity,Subexponential-time algorithms,Exponential-time hypothesis
论文评审过程：Received 3 May 2013, Revised 3 January 2014, Accepted 8 April 2014, Available online 16 April 2014.
论文官网地址：https://doi.org/10.1016/j.jcss.2014.04.015
