ALCOM Seminar: Eric Allender "Grid Graph Reachability Problems"
2006.11.13 |
| Date | Tue Nov 14 |
| Time | 11:15 — 12:00 |
| Location | Ada-018 |
Title: Grid Graph Reachability Problems
Speaker: Eric Allender, Rutgers
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 planardigraphs, and
* reachability on certain classes of grid graphs gives natural examples
of problems that are hard for NC1 under AC0 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:
* Reachability on planar graphs (andgrid graphs) is logspace-equivalent to
reachability on graphs of genus 1. Nothing is known about genus 2 and
higher, except for the trivial NL upper bound.
* Reachability on "layered" grid graphs can be done in UL (a subclass of NL).
* Many of the natural restrictions on grid-graph reachability (GGR) are
equivalent under AC0 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 inmazes studied by Blum and Kozen.
This gives rise to a hierarchy of complexity classes between NC1 and L.
* 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 AC0 reduces to undirected GGR.
* We build on this to show that reachability for single-source
multiple-sink planardags is solvable in DLOG.
This is joint work with DavidA. Mix Barrington, Tanmoy Chakraborty,
Samir Datta, and Sambuddha Roy.
Host: Peter Bro Miltersen