ECCC-Report TR05-148https://eccc.weizmann.ac.il/report/2005/148Comments and Revisions published for TR05-148en-usThu, 08 Dec 2005 00:00:00 +0200
Revision 1
| The Directed Planar Reachability Problem |
Eric Allender,
Samir Datta,
Sambuddha Roy
https://eccc.weizmann.ac.il/report/2005/148#revision1 We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to the planar case. We also consider a previously-studied subclass of planar graphs known as grid graphs. We show that the directed planar s-t-connectivity problem reduces to the reachability problem for directed grid graphs. A special case of the grid-graph reachability problem where no edges are directed from right to left is known as the ``layered grid graph reachability problem''. We show that this problem lies in the complexity class UL.
Thu, 08 Dec 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2005/148#revision1
Paper TR05-148
| The Directed Planar Reachability Problem |
Eric Allender,
Samir Datta,
Sambuddha Roy
https://eccc.weizmann.ac.il/report/2005/148We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to the planar case.
We also consider a previously-studied subclass of planar graphs known as grid graphs. We show that the directed planar s-t-connectivity problem reduces to the reachability problem for directed grid graphs.
A special case of the grid-graph reachability problem where no edges are directed from right to left is known as the ``layered grid graph reachability problem''. We show that this problem lies in the complexity class UL.
Wed, 07 Dec 2005 18:54:28 +0200https://eccc.weizmann.ac.il/report/2005/148