__
TR14-008 | 20th January 2014 22:09
__

#### Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

**Abstract:**
The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 n)$ space bound, (2) designing a polynomial-time algorithm with $O(n^{1-\epsilon})$ space bound, and (3) designing an {\em unambiguous} non-deterministic log-space (UL) algorithm. These are well-known open questions in complexity theory, and solving any one of them will be a major breakthrough. We will discuss some of the recent progress reported on these questions for certain subclasses of surface-embedded directed graphs.