## René van Bevern, Hannes Moser, and Rolf Niedermeier.
Approximation and tidying—a problem kernel for *s*-plex cluster
vertex deletion.
*Algorithmica*, 62(3-4):930–950, 2012.

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 based on
“approximation and tidying” for kernelizing vertex
deletion problems whose goal graphs can be
characterized by forbidden induced subgraphs. The
method exploits polynomial-time approximation results
and thus provides a useful link between approximation
and kernelization. Employing “approximation and
tidying”, we develop data reduction rules that, in
O(ksn^2) time, transform an s-Plex Cluster Vertex
Deletion instance with n vertices into an equivalent
instance with O(k^2 s^3) vertices, yielding a problem
kernel. To this end, we also show how to exploit
structural properties of the specific problem in order
to significantly improve the running time of the
proposed kernelization method.

[ bib |
DOI |
slides |
.pdf ]
Back

*This file was generated by
bibtex2html 1.98.*