ECCC-Report TR05-149https://eccc.weizmann.ac.il/report/2005/149Comments and Revisions published for TR05-149en-usFri, 26 May 2006 00:00:00 +0300
Revision 1
| Grid Graph Reachability Problems |
Eric Allender,
David Mix Barrington,
Tanmoy Chakraborty,
Samir Datta,
Sambuddha Roy
https://eccc.weizmann.ac.il/report/2005/149#revision1 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 L; they thus give insight into the structure of L. In addition to explicating the structure of L, 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 L. 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 L.
Fri, 26 May 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2005/149#revision1
Paper TR05-149
| Grid Graph Reachability Problems |
Eric Allender,
David Mix Barrington,
Tanmoy Chakraborty,
Samir Datta,
Sambuddha Roy
https://eccc.weizmann.ac.il/report/2005/149We 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 L; they thus give insight into the structure of L.
In addition to explicating the structure of L, 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 L.
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 L.
Wed, 07 Dec 2005 18:55:06 +0200https://eccc.weizmann.ac.il/report/2005/149