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

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. However, 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 digraphs which are even only 2 vertex deletions away from being a DAG. The subject of this talk is a new algorithm that, for every fixed k, runs in linear time and recognizes digraphs 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 digraphs. This is joint work with Daniel Lokshtanov (University of Bergen, Norway) and Saket Saurabh (The Institute of Mathematical Sciences, India).