The Library
Towards a polynomial kernel for directed feedback vertex set
Tools
Bergougnoux, Benjamin, Eiben, Eduard, Ganian, Robert, Ordyniak, Sebastian and Ramanujan, Maadapuzhi Sridharan (2021) Towards a polynomial kernel for directed feedback vertex set. Algorithmica, 83 (5). pp. 1201-1221. doi:10.1007/s00453-020-00777-5 ISSN 1432-0541.
|
PDF
453_2020_Article_777.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (382Kb) | Preview |
Official URL: https://doi.org/10.1007/s00453-020-00777-5
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 et al. (J ACM 55(5):177–186, 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. Since this problem has remained open in spite of the best efforts of a number of prominent researchers and pioneers in the field, a natural step forward is to study the kernelization complexity of DFVS parameterized by a natural larger parameter. 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
SWORD Depositor: | Library Publications Router | ||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Computer algorithms, Computational complexity, Kernel functions | ||||||||
Journal or Publication Title: | Algorithmica | ||||||||
Publisher: | Springer | ||||||||
ISSN: | 1432-0541 | ||||||||
Official Date: | May 2021 | ||||||||
Dates: |
|
||||||||
Volume: | 83 | ||||||||
Number: | 5 | ||||||||
Page Range: | pp. 1201-1221 | ||||||||
DOI: | 10.1007/s00453-020-00777-5 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Re-use Statement: | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 27 April 2022 | ||||||||
Date of first compliant Open Access: | 27 April 2022 | ||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year