Approximation and Tidying–A Problem Kernel for s‐Plex Cluster Vertex Deletion

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 ²) time, transform an s‐Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O(k ² s ³) 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.