# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Hitting Long Directed Cycles is Fixed-Parameter Tractable

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2003.05267.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### 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 $\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].

$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].