Kernelization Through Tidying: A Case Study Based on s-Plex Cluster Vertex Deletion.

In Proceedings of the 9th Latin American Theoretical Informatics Symposium (LATIN'10), Oaxaca, México, April 2010. Volume 6034 in Lecture Notes in Computer Science, pages 528–539, Springer-Verlag Berlin, Germany.

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²s³)-vertex problem kernel for s-Plex Cluster Vertex Deletion that can be computed in O(ksn²) time, where n is the number of graph vertices. The corresponding "kernelization through tidying" exploits polynomial-time approximation results.

Download

The paper and slides of an accompanying talk are available in PDF format. The original publication can be found via www.springerlink.com.

BibTex Entry

For information on using BibTex in your LaTeX documents, refer to the chapter "Bibliography management" in the wikibook for LaTeX.

@inproceedings{BMN10,
  author = {Ren{\'e} van Bevern and Hannes Moser
    and Rolf Niedermeier},
  title = {Kernelization Through Tidying---A Case Study Based on
    $s$-Plex Cluster Vertex Deletion},
  booktitle = {Proceedings of the 9th Latin American Theoretical
    Informatics Symposium (LATIN'10)},
  publisher = {Springer-Verlag Berlin, Germany},
  address = {Oaxaca, M{\'e}xico},
  year = {2010},
  series = {Lecture Notes in Computer Science},
  pages = {528--539},
  volume = {6034}
}