Information Technology Reference
In-Depth Information
n
2
/
3
(
)
=
(
,
)
is
O
be the input directed planar graph. Let
G
u
be the
underlying undirected graph. The first step is to apply the planar separator algorithm
repeatedly
k
times on the connected components of
G
u
that are bigger than
n
2
/
3
to further partition the graph until every component is of size
.Let
G
V
E
n
2
/
3
. It is easy to
log
n
log
2
3
see that after
k
=
×
)
applications we get a collection
S
of separators
(
9
/
8
n
2
/
3
with total size
O
(
)
so that removing
S
partitions the graph into disconnected
n
2
/
3
. (This is a standard trick used in
components where each component is of size
many separator-based algorithms). Let
C
1
,
C
2
,...,
C
l
be the set of vertices in these
components.
Now consider the kernel graph
G
=
(V, E)
where
V
=
S
∈{
s
,
t
}
. For any two
nodes
x
and
y
in
is a directed edge if and only if there is a directed path from
x
to
y
in the subgraph of
G
that is induced by
V
,
(
x
,
y
)
C
i
(call this
G
i
), for some connected
component
C
i
in the partition. Clearly, the number of nodes in
V
∈
n
2
/
3
.Now
consider the algorithm that decides whether there is a directed path from
s
to
t
in
G
by performing a BFS on
G
is
O
(
)
?, the
algorithm performs BFSs for each of the graphs
G
i
starting at
x
looking for a path
from
x
to
y
, and returns YES if for some
G
i
this inner BFS returns true. Notice that
since
G
starting at
s
. Whenever BFS queries
(
x
,
y
)
∃
E
n
2
/
3
n
2
/
3
|
V
∈
C
i
|
is at most
O
(
)
, each of this BFSs can be implemented in
O
(
)
n
2
/
3
space and polynomial time. Hence, overall the algorithm takes
O
(
)
space and
polynomial time.
For extending this proof to the
O
n
1
/
2
+
˃
)
n
1
/
2
+
˃
)
(
|
S
|=
(
.
But that will result in large components and a simple application of the inner BFSswill
not give the required space bound. Instead, we can apply the algorithm recursively.
By limiting the number of recursive applications to a constant, we can make sure
that the running time remains polynomial. We omit the details.
space bound, we need
O
Before we move on to the next section we mention that there is a certain computa-
tional model known as NNJAG model in which it is possible to prove lower bounds
those match both Savitch's bound and the BBRS bound [
Poo93
,
CR80
,
EPA99
].
The NNJAG model is a branching program model tailored towards the reachability
problem with restricted access to the input graph. While all the known algorithms
for general reachability (such as BFS, DFS, Savitch's algorithm, BBRS algorithm)
can be implemented in the NNJAG without substantial increase in time and space (in
comparison to implementations on a random access machine), it is not clear to the
author how a general approach such as kernelization can be handled in these models.
It is conceivable that algorithms based on kernelization can overcome NNJAG lower
bounds and help solve these open problems.
3.3 NL Versus UL Problem
The main progress on this problem has also been on graphs with some topological
structure. We first discuss a technique developed by Reinhardt and Allender [
RA00
]
since all the known proofs on this problem use their technique.
