Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion

René van Bevern, Hannes Moser, Rolf Niedermeier

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)


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(ksn2) time, transform an s-PLEX CLUSTER VERTEX DELETION instance with n vertices into an equivalent instance with O(k2s3) 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.

Original languageEnglish
Pages (from-to)930-950
Number of pages21
Issue number3-4
Publication statusPublished - 1 Jan 2012
Externally publishedYes


  • Computational intractability
  • Fixed-parameter tractability
  • Graph-based data clustering
  • NP-hard graph problem
  • Polynomial-time data reduction


Dive into the research topics of 'Approximation and tidying—a problem kernel for s-Plex cluster vertex deletion'. Together they form a unique fingerprint.

Cite this