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.