.png){kind=icon}
.png){kind=icon}
Return
When recursion is better than iteration: A linear-time algorithm for directed acyclicity with few error vertices
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jctb.2025.11.002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Planarity, bipartiteness and (directed) acyclicity are basic graph properties with classic linear-time recognition algorithms. However, the problems of testing whether a given graph has k vertices whose deletion makes it planar, bipartite or a directed acyclic graph (DAG) are all fundamental NP-complete problems when k is part of the input. As a result, a significant amount of research has been devoted to understanding whether, for every fixed k, these problems admit a polynomial-time algorithm (where the exponent in the polynomial is independent of k) and in particular, whether they admit linear-time algorithms. While we now know that for every fixed k, we can test in linear time whether a graph is k vertices away from being planar or bipartite, the best known algorithms in the case of directed acyclicity are the algorithm of Garey and Tarjan [IPL 1978], which runs in time (nk-1 m) and the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008], which runs in time(k! 4k k4 n m), where nand mare the number of vertices and arcs in the input digraph, respectively. In other words, it has remained open whether it is possible to recognize in linear time, a graph that is two vertices away from being acyclic. In this paper, we settle this question by giving an algorithm that decides whether a given graph is k vertices away from being acyclic, in time (k! 4k k5 (n+m)). That is, for every fixed k, our algorithm runs in time (m + n), thus mirroring the case for planarity and bipartiteness. We obtain our algorithm by introducing a general method-ology that shaves off a factor of n from certain algorithms that use the powerful technique of iterative compression. The two main features of our methodology are: (i) This is the first generic technique for designing linear-time FPT algorithms for directed cut problems and (ii) it can be used in combina-tion with future improvements in algorithms for the so-called compression version of other well-studied cut problems such as MULTICUT and DIRECTED SUBSET FEEDBACK VERTEX SET. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keywords:
Directed graphs
Feedback vertex set
Fixed-parameter algorithms
Journal
J
IF:
1.2
Papers:
48
Citations:
0
Organization
View more organizations