zbMATH — the first resource for mathematics

A more effective linear kernelization for cluster editing. (English) Zbl 1176.05078
Chen, Bo (ed.) et al., Combinatorics, algorithms, probabilistic and experimental methodologies. First international symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-74449-8/pbk). Lecture Notes in Computer Science 4614, 36-47 (2007).
Summary: In the NP-hard Cluster Editing problem, we have as input an undirected graph \(G\) and an integer \(k \geq 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 R. Fellows [“The lost continent of polynomial time: Preprocessing and kernelization”, Lect. Notes Comput. Sci. 4169, 276–277 (2006; Zbl 1154.68560)] 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 \geq 0\), finds a graph \(G^{\prime}\) and an integer \(k^{\prime} \leq k\) such that \(G\) can be transformed into a cluster graph by at most \(k\) edge modifications iff \(G^{\prime}\) can be transformed into a cluster graph by at most \(k^{\prime}\) edge modifications, and the problem kernel \(G^{\prime}\) 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^{\prime}\) can be further improved to \(4k\). 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.
For the entire collection see [Zbl 1122.68003].

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI