zbMATH — the first resource for mathematics

A fast branching algorithm for cluster vertex deletion. (English) Zbl 1330.68220
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. 9th international computer science symposium in Russia, CSR 2014, Moscow, Russia, June 7–11, 2014. Proceedings. Berlin: Springer (ISBN 978-3-319-06685-1/pbk). Lecture Notes in Computer Science 8476, 111-124 (2014).
Summary: In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques).
F. Hüffner et al. [Lect. Notes Comput. Sci. 4957, 711–722 (2008; Zbl 1136.68465); Theory Comput. Syst. 47, No. 1, 196–217 (2010; Zbl 1205.68263)] initiated the parameterized study of cluster vertex deletion, where the allowed modification is vertex deletion, and presented an elegant \(\mathcal{O}(2^k k^9 + nm)\)-time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for Cluster Vertex Deletion and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the \(2^{k }\)-barrier for cluster vertex deletion and present an \(\mathcal{O}(1.9102^k (n+m))\)-time branching algorithm.
For the entire collection see [Zbl 1290.68009].

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