License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.36
URN: urn:nbn:de:0030-drops-81126
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8112/
Go to the corresponding LIPIcs Volume Portal


Bergougnoux, Benjamin ; Eiben, Eduard ; Ganian, Robert ; Ordyniak, Sebastian ; Ramanujan, M. S.

Towards a Polynomial Kernel for Directed Feedback Vertex Set

pdf-format:
LIPIcs-MFCS-2017-36.pdf (0.5 MB)


Abstract

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph D and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every directed cycle of D. DFVS was shown to be fixed-parameter tractable when parameterized by solution size by Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]; since then, the existence of a polynomial kernel for this problem has become one of the largest open problems in the area of parameterized algorithmics. In this paper, we study DFVS parameterized by the feedback vertex set number of the underlying undirected graph. We provide two main contributions: a polynomial kernel for this problem on general instances, and a linear kernel for the case where the input digraph is embeddable on a surface of bounded genus.

BibTeX - Entry

@InProceedings{benjamin_et_al:LIPIcs:2017:8112,
  author =	{Benjamin Bergougnoux and Eduard Eiben and Robert Ganian and Sebastian Ordyniak and M. S. Ramanujan},
  title =	{{Towards a Polynomial Kernel for Directed Feedback Vertex Set}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8112},
  URN =		{urn:nbn:de:0030-drops-81126},
  doi =		{10.4230/LIPIcs.MFCS.2017.36},
  annote =	{Keywords: parameterized algorithms, kernelization, (directed) feedback vertex set}
}

Keywords: parameterized algorithms, kernelization, (directed) feedback vertex set
Seminar: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 22.11.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI