Towards a Polynomial Kernel for Directed Feedback Vertex Set

D 2017

Towards a Polynomial Kernel for Directed Feedback Vertex Set

EIBEN, Eduard, Sebastian ORDYNIAK, M.S. RAMANUJAN, Benjamin BERGOUGNOUX, Robert GANIAN et. al.

Basic information

Original name

Towards a Polynomial Kernel for Directed Feedback Vertex Set

Authors

EIBEN, Eduard (703 Slovakia), Sebastian ORDYNIAK (276 Germany), M.S. RAMANUJAN (356 India), Benjamin BERGOUGNOUX (250 France) and Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution)

Edition

83. vyd. Nemecko, 42nd International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2017, August 21-25, 2017 - Aalborg, Denmark, p. 1-15, 15 pp. 2017

Publisher

LIPIcs

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

URL

RIV identification code

RIV/00216224:14330/17:00100550

Organization unit

Faculty of Informatics

ISBN

978-3-95977-046-0

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36

Keywords in English

parameterized algorithms; kernelization; (directed) feedback vertex set

Abstract

V originále

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.

Citovat

EIBEN, Eduard, Sebastian ORDYNIAK, M.S. RAMANUJAN, Benjamin BERGOUGNOUX and Robert GANIAN. Towards a Polynomial Kernel for Directed Feedback Vertex Set. Online. In Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin. 42nd International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2017, August 21-25, 2017 - Aalborg, Denmark. 83rd ed. Nemecko: LIPIcs, 2017, p. 1-15. ISBN 978-3-95977-046-0. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36.

@inproceedings{1414043,
   author = {Eiben, Eduard and Ordyniak, Sebastian and Ramanujan, M.S. and Bergougnoux, Benjamin and Ganian, Robert},
   address = {Nemecko},
   booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science, {MFCS} 2017, August 21-25, 2017 - Aalborg, Denmark},
   doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36},
   edition = {83},
   editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
   keywords = {parameterized algorithms; kernelization; (directed) feedback vertex set},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Nemecko},
   isbn = {978-3-95977-046-0},
   pages = {1-15},
   publisher = {LIPIcs},
   title = {Towards a Polynomial Kernel for Directed Feedback Vertex Set},
   url = {http://drops.dagstuhl.de/opus/volltexte/2017/8112/},
   year = {2017}
}

TY  - JOUR
ID  - 1414043
AU  - Eiben, Eduard - Ordyniak, Sebastian - Ramanujan, M.S. - Bergougnoux, Benjamin - Ganian, Robert
PY  - 2017
TI  - Towards a Polynomial Kernel for Directed Feedback Vertex Set
PB  - LIPIcs
CY  - Nemecko
SN  - 9783959770460
KW  - parameterized algorithms
KW  - kernelization
KW  - (directed) feedback vertex set
UR  - http://drops.dagstuhl.de/opus/volltexte/2017/8112/
L2  - http://drops.dagstuhl.de/opus/volltexte/2017/8112/
N2  - 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.
ER  -

EIBEN, Eduard, Sebastian ORDYNIAK, M.S. RAMANUJAN, Benjamin BERGOUGNOUX and Robert GANIAN. Towards a Polynomial Kernel for Directed Feedback Vertex Set. Online. In Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin. \textit{42nd International Symposium on Mathematical Foundations of Computer Science, $\{$MFCS$\}$ 2017, August 21-25, 2017 - Aalborg, Denmark}. 83rd ed. Nemecko: LIPIcs, 2017, p.~1-15. ISBN~978-3-95977-046-0. Available from: https://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36.

Detailed Information on Publication Record