A 2k kernel for the cluster editing problem Conference Paper uri icon

abstract

  • 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 kk, 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. 2011 Elsevier Inc. All rights reserved.

published proceedings

  • Journal of Computer and System Sciences

author list (cited authors)

  • Chen, J., & Meng, J.

citation count

  • 45

complete list of authors

  • Chen, Jianer||Meng, Jie

publication date

  • January 2012