Information Technology Reference
In-Depth Information
n
1
−
˃
)
n
1
−
˃
)
=
g
=
(
(
bound. For
m
space algorithm with polynomial
running time for reachability, for any small constant
˃
, improving the BBRS bound.
One of the motivations for investigating the reachability problem for this class
of surface-embedded graphs comes from earlier work due to Allender, Barring-
ton, Chakraborthy, Datta, and Roy [
ABC+09
]. In [
ABC+09
], the authors considered
reachability in planar DAGs with a
single
source vertex. They called this class of
graphs Single source Multiple sink Planar Dags (SMPD). SMPD generalizes Single
source Single sink Planar Dags (SSPD). SSPDs are interesting since they generalize
series parallel graphs
which is a well-studied restriction of directed acyclic graphs.
Allender et al. presented a log-space algorithm for reachability in SMPDand left open
whether reachability can be solved using logarithmic space over planar DAGs with
multiple source nodes. In [
SBV10
], building on the SMPD algorithm, we present
a log-space algorithm for planar dags with logarithmic number of sources. In the
subsequent paper [
SV12
], via a careful use of techniques developed in [
SBV10
],
we proved the log-space kernelization theorem t
hat i
n particular implied a log-space
algorithm for reach
abil
ity in graphs with 2
O
(
≥
log
n
)
sources, embedded on a sur-
face of genus 2
O
(
≥
log
n
)
. The proof of this theorem is technically involved and we
do not discuss it here. It remains a significant open question whether reachability
for planar Dags (without any restriction on the number of sources) can be solved
deterministically in
o
O
, we get
O
log
2
n
space.
While improving Savitch's bound even for planar graphs remains open, the ques-
tion of improving the BBRS bound for planar graphs was settled recently. Using a
kernelization approach, in [
INP+13
], we show that the directed planar reachability
problem can be solved in polynomial time using roughly
O
(
)
n
1
/
2
space. This result
extends a similar bound for the reachability problem over
grid graphs
due to Asano
and Doerr [
AD11
].
(
)
Theorem 2
[
INP+13
]
For any constant
0
2
, there is an algorithm that,
given a directed planar graph G and two vertices s and t , decides whether there is
a path from s to t . This algorithm runs in time n
O
(
1
/˃)
< ˃ <
1
/
n
1
/
2
+
˃
)
and uses O
(
space,
where n is the number of vertices of G.
(
≥
n
O
For showing this result, we first design a polynomial-time and
)
-space
(
≥
n
algorithm for computing a “separator” of
O
size for an undirected planar graph.
(For any undirected graph
G
and for any constant
ʻ
,0
)
1, a
ʻ
-separator
of
G
is a a subset of vertices
S
whose removal disconnects
G
into two subgraphs
A
and
B
,
such that
< ʻ <
is at most
ʻ
n
). This algorithm is based on a parallel algorithm
for constructing a planar separator due to Gazit and Miller [
GM87
].
|
A
|
and
|
B
|
Theorem 3
[
INP+13
]
There is an algorithm that takes an undirected plan
ar
graph
G with n vertices as input and outputs a (8/9)-se
pa
rator of G of size O
(
≥
n
)
. This
(
≥
n
O
O
algorithm runs in polynomial time and uses
)
space. (Here
(
s
(
n
))
denotes
O
(
1
)
)
O
(
s
(
n
)(
log
n
)
).
n
1
/
2
+
˃
)
Proof Sketch
While for obtaining the
O
space bound we need a recur-
sive approach, it is easy to illustrate the idea for the case when the space bound
(
