Information Technology Reference
In-Depth Information
(
,
,
)
be an input instance of REACH. Given as additional input the number
N
i
of vertices in
G
that are reachable from
s
by directed paths of length at most
i
.
Design an NL algorithm that on each accepting computation path halts with the
number
N
i
+
1
as the contents of the worktape.
4. Put these parts together to obtain an NL algorithm for REACH.
In the 1970s Savitch's theorem [
Pap94
, Theorem 7.5] had already shown that
nondeterministic space is quite different from nondeterministic time.
Theorem 5.3
(Savitch)
For any space-constructible function s
3. Let
G
s
t
(
n
)
≥
log
n we have
s
2
NSPACE
.
Exercise
Show that REACH is in DSPACE
[
s
(
n
)
]ↆ
DSPACE
[
(
n
)
]
log
2
n
using the following divide and
conquer strategy: there is an
s
-to-
t
directed path in
G
of length
k
if and only if for
some vertex
r
of
G
there is a directed
s
-to-
r
path of length
[
]
k
/
2
and a directed
r
-to-
t
path of length
in
G
.
The above results definitely encourage the optimist to believe that it is possible
to design a deterministic logspace algorithm for REACH and hence show NL
k
/
2
L.
Vinodchandran's article surveys recent progress on space-bounded algorithms for
REACH. A big breakthrough was obtained by Reingold [
Rei08
] in 2004 by showing
that
undirected
graph reachability is in L. We discuss some aspects of Reingold's
result in the Sect.
1.6
.
=
1.6 Undirected Graph Reachability
In this section we develop the background and outline some of the ideas that are
involved in the proof of Reingold's theorem [
Rei08
] which states that undirected
graph reachability is in L.
The corresponding language we denote as UREACH: UREACH
={
G
,
s
,
t
|
G
is an undirected graph containing a path from
s
to
t
}
. Clearly, UREACH is a special
case of REACH and hence is in NL.
First, we note that without loss of generality we can assume the undirected graph
G
is 3-regular. That is to say, every vertex in the graph
G
has degree exactly 3.
More precisely, given an instance
of UREACH, there is a determinis-
tic logspace computation that we can apply to transform it into another instance
G
,
s
,
t
G
,
s
,
t
in which
G
is 3-regular such that
G
,
s
,
t
∈
UREACH if and only if
G
,
s
,
t
∈
UREACH. The main idea involved in this transformation is that a vertex
v
3 can be replaced by a cycle of length
d
consisting of vertices
v
1
,v
2
, ..., v
d
, and the
i
th neighbor of
in
G
of degree
d
>
v
(say, in lexicographic order) made adjacent
to
v
i
. This transformation can be carried out in logspace and in the transformed graph
there is a path between
s
and
t
if and only if there is one in
G
. Repeated application of
this step takes care of all vertices in
G
of degree more than 3. Vertices of degree 1 or
2 can be contracted (taking appropriate care if
s
or
t
is encountered in the contraction
process).
Exercise
Verify the details of the logspace transformation sketched above.
