International Conference on Algorithms and Complexity (CIAC 2019)

Publications

Now showing1 - 1 of 1

Some of the metrics are blocked by your
consent settings
Access status: without files ,
Parameterized Algorithms for generalizations of directed feedback vertex set
(Springer, 2019)
Göke, Alexander
;
Marx, Dániel
;
Mnich, Matthias
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.
Publicationtype: Conference Paper
170