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: Lecture Notes in Computer Science, 11485 LNCS: 249-261 (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.
URI: http://hdl.handle.net/11420/4604
ISBN: 978-303017401-9
ISSN: 0302-9743
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

51
Last Week
0
Last month
10
checked on Sep 30, 2020

Google ScholarTM

Check

Add Files to Item

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.