Options
Parameterized Algorithms for generalizations of directed feedback vertex set
Publikationstyp
Conference Paper
Date Issued
2019
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
11485 LNCS
Start Page
249
End Page
261
Citation
11th International Conference on Algorithms and Complexity (CIAC 2019)
Contribution to Conference
Publisher DOI
Publisher
Springer
The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a -time algorithm, where. Here we show fixed-parameter tractability of two generalizations of DFVS: Find a smallest vertex set S such that every strong component of has size at most s: we give an algorithm solving this problem in time. Find a smallest vertex set S such that every non-trivial strong component of is 1-out-regular: we give an algorithm solving this problem in time. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.
DDC Class
004: Informatik