A more effective linear kernelization for cluster editing

Abstract: In the NP-hard Cluster Editing problem, we have as input an undirected graph and an integer . The question is whether we can transform , by inserting and deleting at most 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 vertices. More precisely, we present a cubic-time algorithm that, given a graph and an integer , finds a graph and an integer such that can be transformed into a cluster graph by at most edge modifications iff can be transformed into a cluster graph by at most edge modifications, and the problem kernel has at most vertices. So far, only a problem kernel of vertices was known. Second, we show that this bound for the number of vertices of can be further improved to 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 . We present a simple kernelization for this variant leaving a problem kernel of at most vertices. [Copyright &y& Elsevier]