Chennai Mathematical Institute

Seminars




Reachability in Single Source Planar DAGs
Tanmoy Chakraborty
Chennai Mathematical Institute.
09-11-05


Abstract

Reachability in a directed graph is the problem of determining whether there exists a directed path from one given vertex to another. This problem is known to be complete for Nondeterministic Logspace (NL). Previous work ([JLR01] has looked at reachability in series-parallel graphs (a special case of planar DAGs) and shown it to be complete for Logspace (L), a class which is presumably smaller than NL. Another line of work ([ADR05]) investigated general Planar Reachability and only succeeded in reducing it to its complement. We generalize [JLR01] to show that Reachability in Planar Directed Acyclic Graphs with one source (a zero indegree vertex), is complete for L. In addition, we show how to recognize Single Source Planar DAGs in L.

This is joint work with Eric Allender (Rutgers U.), Dave Barrington (U. Mass.), Samir Datta (CMI) and Sambuddha Roy (Rutgers U.).