We use cookies on this site. By browsing our site you agree to our use of cookies. Close this message Find out more

Home > Computer Science home > Events > Seminar Ramanujan Sridharan
More in this section Events articles

Seminar Ramanujan Sridharan

21/11/2017 (15:00-16:00)

Ramanujan Sridharan

Ramanujan Sridharan, Technische Universität Wien

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


Comment on this page

Did you find the information you were looking for? Is there a broken link or content that needs updating? Let us know so we can improve the page.

Note: If you need further information or have a question that cannot be satisfied by this page, please call our switchboard on +44 (0)1784 434455.

This window will close when you submit your comment.

Add Your Feedback