License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.59
URN: urn:nbn:de:0030-drops-124664
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12466/
Go to the corresponding LIPIcs Volume Portal

Göke, Alexander ; Marx, Dániel ; Mnich, Matthias

Hitting Long Directed Cycles Is Fixed-Parameter Tractable

pdf-format:
LIPIcs-ICALP-2020-59.pdf (0.6 MB)

Abstract

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 2^O(ℓ^6 + ℓ k^3 log k + k^5 log k log ℓ) ⋅ n^O(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].

BibTeX - Entry

@InProceedings{gke_et_al:LIPIcs:2020:12466,
  author =	{Alexander G{\"o}ke and D{\'a}niel Marx and Matthias Mnich},
  title =	{{Hitting Long Directed Cycles Is Fixed-Parameter Tractable}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12466},
  URN =		{urn:nbn:de:0030-drops-124664},
  doi =		{10.4230/LIPIcs.ICALP.2020.59},
  annote =	{Keywords: Directed graphs, directed feedback vertex set, circumference}
}

Keywords: Directed graphs, directed feedback vertex set, circumference
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI