Information Technology Reference
In-Depth Information
The following lemma establishes Theorem 6.
Lemma 8
Let G be a directed planar graph. Then with respect to the weight function
w
g
t
, for every pair of nodes u and
v
, if there is a directed path from u to
v
, then there
is a
unique
path from u to
v
of minimum weight.
Proof
Suppose there are
u
paths
P
1
and
P
2
of minimum
weight. We assume that the paths do not intersect on vertices other than the end
points (otherwise we can find two vertices
u
≤
and
,v
so that there are two
u
to
v
v
≤
along these paths that satisfies
this property using a standard cut-and-paste argument and use these vertices instead).
We have
. Now consider the graph
G
≤
that is same as
G
except that
the path
P
2
is reversed so that the set of edges
w
g
t
(
P
1
)
=
w
g
t
(
P
2
)
(
P
1
,
−
P
2
)
becomes a simple cycle
in
G
≤
(
−
P
2
denotes the reversed path). Let
C
denote this cycle. Then
w
g
t
(
C
)
=
w
g
t
(
0. The second equality because of
the skew-symmetry of the weight function. This contradicts Lemma 7.
P
1
)
+
w
g
t
(
−
P
2
)
=
w
g
t
(
P
1
)
−
w
g
t
(
P
2
)
=
It is clear that we can use Green's Theorem to design a class of min-unique weight
functions. In fact any “nice” solution to the differential equation
∂
Q
∂
x
∂
y
−
∂
P
=
1will
−
y
2
x
2
yield such a weight function. For example, setting
P
(
x
,
y
)
=
and
Q
(
x
,
y
)
=
to the left-hand side of Green's theorem yields the weight function
w(
e
)
=
(
x
u
y
v
−
x
which is also min-unique.
Can we use such geometric techniques to design min-unique weight functions
for larger classes of graphs? In [
BTV09
] it is observed that reachability in layered
grid graphs over three dimensions is complete for
NL
. It might be possible to use
generalizations of Green's theorem (such as Stokes' theorem) to design a min-unique
weight function for three-dimensional layered grid graphs.
y
u
)
v
3.4 The BBRS Bound
We present the algorithm due to Barnes, Buss, Ruzzo, and Schieber [
BBRS98
] that
solves the directed graph reachability problem in sub-linear space and polynomial
time.
Theorem 9
[
BBRS98
]
For any k, there is a polynomial-time algorithm that given
a directed graph G and two nodes s and t , decides whether there is a path from s to
t in space O
n
(
2
k
≥
log
n
)
, where n is the number of vertices of G.
Proof
The algorithm uses a combi
nati
on of BFS and Savitch's algorithm. For a
parameter
ʲ
(this will be set to 2
k
≥
log
n
to get the desired bound), it constructs the
levels of BFS tree that are at
ʲ
distance apart. Divide the vertex set into levels
according to distance from
s
. That is, the level
i
vertex set is defined as:
V
i
={
v
|
d
(
s
,v)
=
i
}
,
where
d
is the distance function
.
