Information Technology Reference
In-Depth Information
(1) algorithms that beat both Savitch's bound and the BBRS bound for a subclass
of directed
acyclic
graphs parameterized by the number of sources and the genus of
the embedding [
SBV10
,
SV12
] (2) an algorithm for directed planar reachability that
improves on the BBRS bound [
INP+13
]. The main approach in both these results is
that of space-efficient “kernelization.”
Kernelization is a known preprocessing technique in designing algorithms (for
example in the area of fixed parameter tractability). Kernelization algorithms are
reductions from a problem to itself so that the easy part of the instance is abstracted
out and the core part is retained in the reduced instance. The hope is that the core part
will be of smaller size and hence known algorithms can be applied to this compressed
instance yielding algorithms with better complexity. We first illustrate this in a simple
scenario.
Consider a reachability instance
is a
n
-vertex graph
with the guarantee that it has at most
k
directed edges (the remaining edges are
undirected). Let
G
un
be the undirected graph we get by removing all the directed
edges from
G
. For a directed edge
e
∗
G
,
s
,
t
ↆ
where
G
=
(
V
,
E
)
=
(
u
,v)
let
tail
(
e
)
=
u
and
head
(
e
)
=
v
.We
show a simple log-space reduction that takes
∗
G
,
s
,
t
ↆ
and produces a reachability
G
≤
,
s
≤
,
t
≤
ↆ
where
G
≤
is a directed graph with
O
instance
∗
(
k
)
vertices.
In the reduced graph
G
≤
V
≤
,
E
≤
)
,
V
≤
s
≤
,
t
≤
}∈{
v
e
=
(
={
|
e
is a directed edge
E
≤
in
G
}
. The pair
(v
e
1
,v
e
2
)
∃
if
tail
(
e
2
)
is in the same connected component as
V
≤
,
s
≤
,v
e
)
∃
E
≤
head
(
e
1
)
in
G
un
.Fora
v
e
∃
(
if
tail
(
e
)
is in the same connected
t
≤
)
component of
s
in
G
un
and
is in the same connected component
of
t
in
G
un
. Notice that this reduction is log-space since for checking whether two
vertices
u
(v
e
,
if
head
(
e
)
,v
are in the same connected component of
G
un
, we can use Reingold's
log-space algorithm for undirected reachability. It is clear that there is a
s
-
t
path in
G
if and only if there is a
s
≤
-
t
≤
path in
G
≤
. Using this reduction together with Savitch's
algorithm we get that reachability in graphs with
n
o
(
1
)
directed edges can be solved
in
o
log
2
n
(
)
. Also, by applying BFS to the reduced graph, we get that for any
˃ >
0,
n
1
−
˃
)
reachability in graphs with
O
(
directed edges can be solved in polynomial time
n
1
−
˃
)
and
O
space.
We now describe the main kernelization result of [
SBV10
,
SV12
] and its appli-
cation. Let
(
source vertices
embedded on a surface (orientable or non-orientable) of genus at most
g
=
g(
G(
m
, g)
denote the class of DAGs with at most
m
=
m
(
n
)
,
where
n
is the number of vertices. Building on [
SBV10
], in [
SV12
] we show the
following reduction for graphs in
n
)
.
Theorem 1
[
SV12
]
There is a log-space reduction that, given an instance
G(
m
, g)
∗
G
,
s
,
t
ↆ
(presented as a combinatorial embedding) where G
∃
G(
m
, g)
and s
,
t are vertices
t
≤
vertices
of G
≤
, so that (a) there is a directed path from s to t in G if and only if there is a
directed path from s
≤
to t
≤
in G
≤
,(b)G
≤
has O
G
≤
,
s
≤
,
t
≤
ↆ
where G
≤
is a directed graph and s
≤
,
of G, outputs an instance
∗
vertices.
B
y co
mbining the above reduction with Savitch's theor
em
(with
m
(
m
+
g)
=
g
=
2
O
(
≥
log
n
)
) we get that reacha
bility
over graphs with 2
O
(
≥
log
n
)
sources embed-
ded on a surface of genus 2
O
(
≥
log
n
)
can be decided in deterministic log-space. For
m
n
o
(
1
)
we get
o
log
2
n
=
g
=
(
)
space algorithm for reachability that beats Savitch's
