Publisher DOI: | 10.1007/978-3-030-17402-6_21 | Title: | Parameterized Algorithms for generalizations of directed feedback vertex set | Language: | English | Authors: | Göke, Alexander Marx, Dániel Mnich, Matthias ![]() |
Issue Date: | 2019 | Source: | 11th International Conference on Algorithms and Complexity (CIAC 2019) | Journal or Series Name: | Lecture notes in computer science | Abstract (english): | 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. |
Conference: | 11th International Conference on Algorithms and Complexity (CIAC 2019) | URI: | http://hdl.handle.net/11420/4604 | ISBN: | 978-303017401-9 | ISSN: | 0302-9743 | Document Type: | Chapter/Article (Proceedings) |
Appears in Collections: | Publications without fulltext |
Show full item record
Add Files to Item
Note about this record
Cite this record
Export
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.