The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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.STACS.2016.55
URN: urn:nbn:de:0030-drops-57569
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5756/
Go to the corresponding LIPIcs Volume Portal

Mnich, Matthias ; van Leeuwen, Erik Jan

Polynomial Kernels for Deletion to Classes of Acyclic Digraphs

pdf-format:
56.pdf (0.6 MB)

Abstract

We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made.

In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

BibTeX - Entry

@InProceedings{mnich_et_al:LIPIcs:2016:5756,
  author =	{Matthias Mnich and Erik Jan van Leeuwen},
  title =	{{Polynomial Kernels for Deletion to Classes of Acyclic Digraphs}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5756},
  URN =		{urn:nbn:de:0030-drops-57569},
  doi =		{10.4230/LIPIcs.STACS.2016.55},
  annote =	{Keywords: directed feedback vertex/arc set, parameterized algorithms, kernels}
}

Keywords: directed feedback vertex/arc set, parameterized algorithms, kernels
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

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