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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10200 1.2 Computer and information sciences
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
RIV identification code RIV/00216224:14330/17:00100550
Organization unit Faculty of Informatics
ISBN 978-3-95977-046-0
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.36
Keywords in English parameterized algorithms; kernelization; (directed) feedback vertex set
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 7/1/2019 14:00.
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.
PrintDisplayed: 19/7/2024 01:42