Kernelization through tidying: A case study based on s-plex cluster vertex deletion

René Van Bevern, Hannes Moser, Rolf Niedermeier

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

4 Citations (Scopus)

Abstract

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 for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k 2 s3)-vertex problem kernel for s -Plex Cluster Vertex Deletion that can be computed in O(ksn2) time, where n is the number of graph vertices. The corresponding "kernelization through tidying" exploits polynomial-time approximation results.

Original languageEnglish
Title of host publicationLATIN 2010
Subtitle of host publicationTheoretical Informatics - 9th Latin American Symposium, Proceedings
Pages527-538
Number of pages12
DOIs
Publication statusPublished - 18 Jun 2010
Externally publishedYes
Event9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico
Duration: 19 Apr 201023 Apr 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6034 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th Latin American Theoretical Informatics Symposium, LATIN 2010
CountryMexico
CityOaxaca
Period19.04.201023.04.2010

Fingerprint Dive into the research topics of 'Kernelization through tidying: A case study based on s-plex cluster vertex deletion'. Together they form a unique fingerprint.

Cite this