To iterate or not to iterate: A linear time algorithm for recognizing almost-DAGs

Abstract:

Planarity, bipartiteness, and (directed) acyclicity are basic graph properties with classic linear time recognition algorithms and the problems of testing whether a given graph has k vertices whose deletion makes it planar, bipartite, or (directed) acyclic, are fundamental NP-complete problems when k is part of the input. Moreover, it is known that for any fixed k, there is a linear time algorithm to test whether a graph is k vertex deletions away from being planar or bipartite. On the other hand, it has remained open whether there is a similar linear time recognition algorithm for directed graphs which are just 2 vertex deletions away from being a directed acyclic graph.

The subject of this talk is a new algorithm that, for every fixed k,  runs in linear time and recognizes directed graphs which are k vertex deletions away from being acyclic, thus mirroring the case for planarity and bipartiteness.  This algorithm is designed via a new methodology that can be used in combination with the technique of iterative compression from the area of Fixed-Parameter Tractability and applies to several  "cut problems" on directed graphs.