A 2k kernel for the cluster editing problem

作者：Chen Jianer^*; Meng Jie

来源：Journal of Computer and System Sciences, 2012, 78(1): 211-220.

DOI：10.1016/j.jcss.2011.04.001

• NP-hard problem
• Parameterized computation
• Kernelization
• Cluster editing
• Critical clique

The CLUSTER EDITING problem is a decision problem that, for a graph G and a parameter k, determines if one can apply at most k edge insertion/deletion operations on G so that the resulting graph becomes a union of disjoint cliques. The problem has attracted much attention because of its applications in a variety of areas. In this paper, we present a polynomial-time kernelization algorithm for the problem that produces a kernel of size bounded by 2k. More precisely, we develop an O(mn)-time algorithm that, on a graph G of n vertices and m edges and a parameter k, produces a graph G' and a parameter k' such that k' <= k, that G' has at most 2k' vertices, and that (G, k) is a yes-instance if and only if (G', k') is a yes-instance of the CLUSTER EDITING problem. This improves the previously best kernel of size 4k for the problem.

• 出版日期2012-1