Revision #1 Authors: Eric Allender, Samir Datta, Sambuddha Roy

Accepted on: 8th December 2005 00:00

Downloads: 1613

Keywords:

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.

TR05-148 Authors: Eric Allender, Samir Datta, Sambuddha Roy

Publication: 7th December 2005 18:54

Downloads: 1788

Keywords:

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.