Information Technology Reference
In-Depth Information
1.6.1 Reachability in Graphs of Logarithmic Diameter
Let
G
be a connected undirected graph. For every pair of vertices
u
,v
of
G
let
d
G
(
u
,v)
denote the length of the shortest
u
to
v
path in
G
.The
diameter
of
G
is the maximum
distance max
u
,v
d
G
(
u
,v)
between vertices in
G
. Suppose
c
,
d
>
0 are constants and
is an input instance of UREACH such that the maximum degree of
G
is
d
and the diameter of
G
is bounded by
c
log
n
. There is a simple deterministic logspace
algorithm to check if there is an
s
to
t
path in
G
. Since each vertex
u
of
G
has at most
d
neighbors, its neighborhood
N
G
,
s
,
t
, say in increasing
order of vertex names. Furthermore, we are looking for a path of length at most
c
log
n
from
s
to
t
. We can encode all paths of length
c
log
n
starting from
s
by sequences
d
1
,
(
u
)
can be indexed by
{
1
,
2
,...,
d
}
d
for each
i
. This sequence can be written
down on the worktape using at most
O
d
2
, ...,
d
c
log
n
, where 1
≤
d
i
≤
space and the algorithm can
cycle through all such sequences one by one in lexicographic order. For a sequence
d
1
,
(
c
log
d
log
n
)
u
c
log
n
, where
u
i
is
the
d
i
th neighbor of
u
i
−
1
for each
i
. The algorithm can generate the vertices of this
path one by one. In order to generate
u
i
it only needs to store
i
and
u
i
−
1
which is
O
d
2
, ...,
d
c
log
n
the path in
G
defined by it is
s
=
u
0
,
u
1
, ...,
(
log
n
)
space. The algorithm accepts if
u
i
=
t
for some
i
in some sequence.
in general. However, it turns out, as
shown by Reingold [
Rei08
] that there is a deterministic logspace computation that
transforms an instance
The diameter of
n
-vertex graphs can be
(
n
)
G
,
s
,
t
such that
(i)
s
and
t
are in the same connected component of
G
if and only if
s
and
t
are
connected in
G
.
(ii)
G
is a
d
-regular graph for some constant
d
and has diameter bounded by
c
log
n
for some constant
c
.
Reingold's construction of
G
[
Rei08
] is based on properties of expander graphs
and the explicit construction of expanders. We will not describe the details of his
algorithm. Instead, we will present a randomized logspace algorithm for UREACH
and in the process explain some basic properties of expander graphs.
G
,
s
,
t
of UREACH into an instance
1.6.2 A Randomized Logspace Algorithm for UREACH
A randomized logspace bounded Turing machine is a Turing machine
M
that has, in
addition to a read-only input tape and a logspace bounded worktape, one-way access
to a random tape on which is written the outcome of a sequence of unbiased and
independent random bits and in each time instant the random tape head moves one
step to the right reading the next random bit.
ↆ
ˇ
∗
is said to be in the class RL if there is a random-
ized logspace bounded Turing machine that runs in polynomial time such that
Definition 6.1
A language
L
