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

René van Bevern, Hannes Moser, Rolf Niedermeier

Результат исследования: Научные публикации в периодических изданияхстатья

20 Цитирования (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.

Язык оригиналаанглийский
Страницы (с-по)930-950
Число страниц21
ЖурналAlgorithmica
Том62
Номер выпуска3-4
DOI
СостояниеОпубликовано - 1 янв 2012
Опубликовано для внешнего пользованияДа

    Fingerprint

Цитировать