DIMACS Theoretical Computer Science Seminar

Title: Grid Graph Reachability Problems

Speaker: Eric Allender, Rutgers University

Date: February 7, 2006 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We study the complexity of restricted versions of st-connectivity,
which is the standard complete problem for NL.  Grid graphs are a
useful tool in this regard, since
* reachability on grid graphs is logspace-equivalent to reachability
  in general planar digraphs, and
* reachability on certain classes of grid graphs gives natural examples
  of problems that are hard for NC^1 under AC^0 reductions but are not
  known to be hard for DLOG; they thus give insight into the structure of 
  DLOG.
In addition to explicating the structure of DLOG, another of our goals is
to expand the class of digraphs for which connectivity can be
solved in logspace, by building on the work of Jakoby et al.
who showed that reachability in series-parallel digraphs is solvable in DLOG.

Our main results are:
* Many of the natural restrictions on grid-graph reachability (GGR) are
  equivalent under AC^0 reductions (for instance, undirected GGR,
  out-degree-one GGR, and indegree-one-outdegree-one GGR are all
  equivalent).  These problems are all equivalent to the problem of
  determining if a completed game position in HEX is a winning position, as 
  well as to the problem of reachability in mazes studied by Blum and Kozen.
* Series-Parallel digraphs are a special case of single-source-single-sink
  planar dags; reachability for such graphs logspace reduces to
  single-source-single-sink acyclic grid graphs.  We show that reachability
  on such grid graphs AC^0 reduces to undirected GGR.
* We build on this to show that reachability for single-source
  multiple-sink planar dags is solvable in DLOG.

This is joint work with David A. Mix Barrington, Tanmoy Chakraborty,
Samir Datta, and Sambuddha Roy.