|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
|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
checked on Apr 19, 2021
Add Files to Item
Note about this record
Cite this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.