License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.85
URN: urn:nbn:de:0030-drops-48261
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4826/
Go to the corresponding LIPIcs Volume Portal

Giannopoulou, Archontia C. ; Lokshtanov, Daniel ; Saurabh, Saket ; Suchy, Ondrej

Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)

pdf-format:
10.pdf (0.6 MB)

Abstract

In the Tree Deletion Set problem the input is a graph G together with an integer k. The objective is to determine whether there exists a set S of at most k vertices such that G \ S is a tree. The problem is NP-complete and even NP-hard to approximate within any factor of OPT^c for any constant c. In this paper we give an O(k^5) size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on system of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

BibTeX - Entry

@InProceedings{giannopoulou_et_al:LIPIcs:2014:4826,
  author =	{Archontia C. Giannopoulou and Daniel Lokshtanov and Saket Saurabh and Ondrej Suchy},
  title =	{{Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{85--96},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4826},
  URN =		{urn:nbn:de:0030-drops-48261},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.85},
  annote =	{Keywords: Tree Deletion Set, Feedback Vertex Set, Kernelization, Linear Equations}
}

Keywords: Tree Deletion Set, Feedback Vertex Set, Kernelization, Linear Equations
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI