Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.2883
Publisher DOI: | 10.4230/LIPIcs.ICALP.2020.59 | arXiv ID: | 2003.05267 | Title: | Hitting long directed cycles is fixed-parameter tractable | Language: | English | Authors: | Göke, Alexander Marx, Dániel Mnich, Matthias ![]() |
Keywords: | directed graphs; directed feedback vertex set; circumference | Issue Date: | 2020 | Publisher: | Schloss Dagstuhl Leibniz-Zentrum für Informatik | Source: | International Colloquium on Automata, Languages, and Programming (ICALP 2020) | Abstract (english): | In the Directed Long Cycle Hitting Set problem we are given a directed graph G, and the task is to find a set S of at most k vertices/arcs such that G − S has no cycle of length longer than `. We show that the problem can be solved in time 2O(`6+`k3 log k+k5 log k log `) · nO(1), that is, it is fixed-parameter tractable (FPT) parameterized by k and `. This algorithm can be seen as a far-reaching generalization of the fixed-parameter tractability of Mixed Graph Feedback Vertex Set [Bonsma and Lokshtanov WADS 2011], which is already a common generalization of the fixed-parameter tractability of (undirected) Feedback Vertex Set and the Directed Feedback Vertex Set problems, two classic results in parameterized algorithms. The algorithm requires significant insights into the structure of graphs without directed cycles of length longer than and can be seen as an exact version of the approximation algorithm following from the Erdős-Pósa property for long cycles in directed graphs proved by Kreutzer and Kawarabayashi [STOC 2015]. © Alexander Göke, Dániel Marx, and Matthias Mnich; licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). |
Conference: | 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) | URI: | http://hdl.handle.net/11420/5756 | DOI: | 10.15480/882.2883 | ISBN: | 978-3-95977-138-2 | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Chapter/Article (Proceedings) | Project: | Kernelisierung für große Datenmengen Multivariate Algorithmen für Scheduling mit hoher Multiplizität |
License: | ![]() |
Part of Series: | Leibniz international proceedings in informatics (LIPIcs) | Volume number: | 168 |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
LIPIcs-ICALP-2020-59.pdf | Verlagsversion | 637,93 kB | Adobe PDF | View/Open![]() |
Page view(s)
291
Last Week
1
1
Last month
6
6
checked on Jun 1, 2023
Download(s)
114
checked on Jun 1, 2023
SCOPUSTM
Citations
2
Last Week
1
1
Last month
0
0
checked on Jul 11, 2022
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License