René van Bevern, Hannes Moser, and Rolf Niedermeier. Kernelization through tidying—a case study based on s-plex cluster vertex deletion. In Proceedings of the 9th Latin American Symposium on Theoretical Informatics (LATIN'10), Oaxaca, Mexico, volume 6034 of Lecture Notes in Computer Science, pages 527–538. Springer, 2010. The final version of this article appeared in Algorithmica.

We introduce the NP-hard graph-based data clustering problem s-Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s−1 other vertices; cliques are 1-plexes. We propose a new method for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k^2 s^3)-vertex problem kernel for s-Plex Cluster Vertex Deletion that can be computed in O(ksn^2) time, where n is the number of graph vertices. The corresponding “kernelization through tidying” exploits polynomial-time approximation results.

bib | DOI | slides | journal version ] Back


This file was generated by bibtex2html 1.98.