Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-008 | 20th January 2014 22:09

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

RSS-Feed




TR14-008
Authors: N. V. Vinodchandran
Publication: 20th January 2014 22:26
Downloads: 3156
Keywords: 


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.



ISSN 1433-8092 | Imprint