In the NP-hard Cluster Editing problem, we have as input an undirected graph G and an integer k>=0. The question is whether we can transform G, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for Cluster Editing that leads to a problem kernel with at most 6k vertices. More precisely, we present a cubic-time algorithm that, given a graph G and an integer k>=0, finds a graph G^' and an integer k^'@?k such that G can be transformed into a cluster graph by at most k edge modifications iff G^' can be transformed into a cluster graph by at most k^' edge modifications, and the problem kernel G^' has at most 6k vertices. So far, only a problem kernel of 24k vertices was known. Second, we show that this bound for the number of vertices of G^' can be further improved to 4k vertices. Finally, we consider the variant of Cluster Editing where the number of cliques that the cluster graph can contain is stipulated to be a constant d>0. We present a simple kernelization for this variant leaving a problem kernel of at most (d+2)k+d vertices.
['Jiong Guo']
A more effective linear kernelization for cluster editing