Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Hitting Long Directed Cycles is Fixed-Parameter Tractable


Marx,  Dániel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available

Göke, A., Marx, D., & Mnich, M. (2020). Hitting Long Directed Cycles is Fixed-Parameter Tractable. Retrieved from https://arxiv.org/abs/2003.05267.

Cite as: https://hdl.handle.net/21.11116/0000-0007-4923-0
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 $\ell$. We show that the problem can
be solved in time $2^{\mathcal O(\ell k^3\log k + k^5\log k\log\ell)}\cdot
n^{\mathcal O(1)}$, that is, it is fixed-parameter tractable (FPT)
parameterized by $k$ and $\ell$. This algorithm can be seen as a far-reaching
generalization of the fixed-parameter tractability of {\sc Mixed Graph Feedback
Vertex Set} [Bonsma and Lokshtanov WADS 2011], which is already a common
generalization of the fixed-parameter tractability of (undirected) {\sc
Feedback Vertex Set} and the {\sc Directed Feedback Vertex Set} problems, two
classic results in parameterized algorithms. The algorithm requires significant
insights into the structure of graphs without directed cycles length longer
than $\ell$ and can be seen as an exact version of the approximation algorithm
following from the Erd{\H{o}}s-P{\'o}sa property for long cycles in directed
graphs proved by Kreutzer and Kawarabayashi [STOC 2015].