Alladi Ramakrishnan Hall

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

M. S. Ramanujan

University of Warwick, U.K.

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).