2020/03/05 by Alexander Göke, Dániel Marx, Göke, Alexander +3
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2003.02483
openalex publication_date 2020/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a 4kk! nO(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 4k(ks+k+s)!⋅ nO(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 2O(k3)⋅ nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.