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.
- Computational intractability
- Fixed-parameter tractability
- Graph-based data clustering
- NP-hard graph problem
- Polynomial-time data reduction