## 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.*