Information Technology Reference
In-Depth Information
A positively and polynomially weighted graph is said to be
min-unique
if, between
any two nodes the minimum weight path (if it exists) is unique. Here the weight of a
path is the sum of the weights of its edges. Reinhardt and Allender [
RA00
] showed,
using an adaptation of the inductive counting technique of Immerman [
Imm88
]
and Szelepcsényi [
Sze88
], that the reachability question in min-unique graphs can
be decided in
UL
. They combine this construction with an observation due to
Wigderson [
Wig94
] that the isolation lemma of Mulmuley et al. [
MVV87
] can be
used to nonuniformly assign weights to make a given graph min-unique. These two
steps imply the collapse result that
NL
is in nonuniform
UL
.
Thus a space-efficient derandomization of the isolation lemma will show that
NL
UL
. However, derandomizing isolation lemma in its generality will have
much deeper consequences and is a well-known and difficult open problem [
AM08
].
Instead, a viable and concrete approach for showing
NL
=
UL
is to first consider a
class of graphs over which the reachability problem is
NL
-complete, and prescribe a
deterministic
log-space computable weight function which will make graphs in this
class min-unique.
In [
ABC+09
], the authors solve this min-unique weight assignment problem for
the class of
layered grid graphs
. Layered grid graphs are graphs with vertices on a
n
=
n
grid and the edges that go west-to-east and south-to-north. Subsequently in
[
BTV09
], we showhow to extend this weight function to general grid graphs (without
restriction on the direction of edges). This implied that directed planar reachability
is in
UL
since the directed planar reachability problem is known to be reducible
to the grid graph reachability problem [
ADR05
]. In fact this even implied that the
reachability problem for graphs embedded on constant genus surfaces and graphs
that are
K
3
,
3
-free and
K
5
-free are in
UL
since the reachability problem for these
classes of graphs reduces to the directed planar reachability problem [
KV10
,
TW09
]
in log-space.
While, in [
BTV09
] we showed that directed planar reachability is in
UL
, it was not
clear then how to solve the min-unique weight assignment problem for planar graphs.
In a subsequent chapter, we solve this problem using
Green's Theorem
, a celebrated
result from multivariate calculus [
TV12
]. Since it is a slightly nonstandard approach
to use an analytical result to solve discrete problems, we believe this approach has
the potential to solve the general
NL
versus
UL
problem. We next present the proof
of the min-unique weight assignment problem for directed planar graphs based on
Green's theorem.
Green's theorem, stated below, relates a certain curve integral over a closed curve
on the plane to a related double integral over the region enclosed by this curve.
×
Theorem 4
Green's Theorem
Let C be a closed, piecewise smooth, simple curve
on the plane which is oriented counterclockwise. Let R
C
be the region bounded by
C . Let P and Q be functions of
defined on a region containing R
C
that have
continuous partial derivatives in the region. Then
(
x
,
y
)
∂
Q
∂
x
−
dA
∂
P
∂
y
C
(
Pdx
+
Qdy
)
=
R
C
