Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set

Matthias Mnich

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 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a 4^k k! n^{O(1)}-time algorithm, where k = |S|.

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)! n^{O(1)}.

- 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^{O(k^3)}n^{O(1)}. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.

(joint work with Alexander Göke and Dániel Marx)