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.MFCS.2017.36
URN: urn:nbn:de:0030-drops-81126
URL: http://dagstuhl.sunsite.rwth-aachen.de/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
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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