TY - JOUR

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

AU - van Bevern, René

AU - Moser, Hannes

AU - Niedermeier, Rolf

PY - 2012/1/1

Y1 - 2012/1/1

N2 - 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.

AB - 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.

KW - Computational intractability

KW - Fixed-parameter tractability

KW - Graph-based data clustering

KW - NP-hard graph problem

KW - Polynomial-time data reduction

UR - http://www.scopus.com/inward/record.url?scp=79251532855&partnerID=8YFLogxK

U2 - 10.1007/s00453-011-9492-7

DO - 10.1007/s00453-011-9492-7

M3 - Article

AN - SCOPUS:79251532855

VL - 62

SP - 930

EP - 950

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3-4

ER -