@online{Goeke_arXiv2003.02483,
TITLE = {Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set},
AUTHOR = {G{\"o}ke, Alexander and Marx, D{\'a}niel and Mnich, Matthias},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2003.02483},
EPRINT = {2003.02483},
EPRINTTYPE = {arXiv},
YEAR = {2020},
MARGINALMARK = {$\bullet$},
ABSTRACT = {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 $\mathsf{NP}$-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a $4^kk! n^{\mathcal{O}(1)}$-time algorithm, where $k = |S|$. Here we show fixed-parameter tractability of two generalizations of DFVS: -- Find a smallest vertex set $S$ such that every strong component of $G -- S$ has size at most~$s$: we give an algorithm solving this problem in time $4^k(ks+k+s)!\cdot n^{\mathcal{O}(1)}$. This generalizes an algorithm by Xiao [JCSS 2017] for the undirected version of the problem. -- Find a smallest vertex set $S$ such that every non-trivial strong component of $G -- S$ is 1-out-regular: we give an algorithm solving this problem in time $2^{\mathcal{O}(k^3)}\cdot n^{\mathcal{O}(1)}$. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.},
}