Information Technology Reference
In-Depth Information
Chapter 3
Space Complexity of the Directed Reachability
Problem over Surface-Embedded Graphs
N. Variyam Vinodchandran
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 problemover directed graphs are: (1) improv-
ing Savitch's
O
log
2
n
(
)
space bound, (2) designing a polynomial-time algorithm
n
1
−
˃
)
with
O
space bound, and (3) designing an
unambiguous
non-deterministic
log-space (UL) algorithm. These are well-known open questions in complexity the-
ory, and solving any one of them will be a major breakthrough. We discuss some
of the recent progress reported on these questions for certain subclasses of surface-
embedded directed graphs.
(
·
·
Keywords
Graph reachability
Space-bounded computation
Computational
complexity
Mathematics Subject Classification (2010)
Primary 68Q15
3.1 Introduction
The graph reachability problem, the problem of deciding whether there is a path
from a given vertex
s
to a vertex
t
in a given graph, is central to space-bounded
computations. Various versions of this problem characterize several important space
complexity classes. Over directed graphs, it is the canonical complete problem for
Supported in part by the NSF grant CCF-0916525.
