Title: The directed planar reachability problem
Speaker: Sambuddha Roy, Rutgers University
Date: November 22, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We investigate the s-t reachability problem for directed planar graphs, which is hard for L and contained in NL but not known to be complete. We show that this problem logspace-reduces to its complement, and we also show that the problem of searching digraphs in genus 1 (toroidal graphs) reduces to the planar case.
We also consider a previously-studied class of planar graphs known as grid graphs. We show that the directed planar s-t connectivity problem (logspace-)reduces to the reachability problem for directed grid graphs.
We also define a layered version of grid graphs and call it LGGR, and we prove that reachability in such graphs is in the complexity class UL.
We also mention ongoing work about various classes of directed planar graphs in which reachability can be done in Logspace.
This is joint work with Eric Allender and Samir Datta.