Lecture Series / Conference / Course :

Video File:

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

Subject:

Start Time:

14:00

End Time:

15:30

Date:

Tuesday, October 24, 2017

Short Title:

A linear time algorithm for recognizing almost DAGs