New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs STOC ’20, June 22–26, 2020, Chicago, IL, USA
1.3 Results
Our main result is a new elegant algorithm for the incremental
SSSP problem in weighted digraphs.
Theorem 1.1. There is a deterministic algorithm that given a
weighted digraph
𝐺 = (𝑉, 𝐸)
subject to
Δ
edge insertions and weight
decreases, a vertex
𝑠 ∈ 𝑉
, and
𝜖 >
0, maintains for every vertex
𝑣
an estimate
ˆ
𝑑 (𝑣)
such that after every update
𝑑 (𝑠, 𝑣) ≤
ˆ
𝑑 (𝑣) ≤
(
1
+ 𝜖)𝑑 (𝑠, 𝑣)
, and runs in total time
˜
𝑂 (𝑛
2
log𝑊 /𝜖
2.5
+ Δ)
. Path
queries are answered take time linear in the number of path edges.
Our result is the rst deterministic partially dynamic directed
SSSP algorithm to improve over the long-standing
𝑂 (𝑚𝑛)
time
bound achieved by the ES-tree [
53
]. Our result is essentially optimal
for very dense graphs, and is the rst algorithm with essentially
optimal update time for any density in directed graphs. Furthermore,
our algorithm further improves on the randomized
𝑚𝑛
0.9+𝑜 (1)
log𝑊
time algorithm of Henzinger et al. [
40
] if
𝑚 = 𝜔 (𝑛
1.1
)
(their paper
presents only in the decremental setting, but it appears to extend
to the incremental setting as well).
A further strength of our algorithm is that in addition to re-
turning distance estimates, it can also return the corresponding
approximate shortest paths, i.e. it is path-reporting. Previously
known path-reporting dynamic SSSP algorithms in the directed
setting except for the ES-tree are randomized against an oblivious
adversary. In this setting, we in fact also improve for undirected
graphs where the only path-reporting deterministic (or adaptive)
algorithms are the
˜
𝑂 (𝑚
7/4
𝑛
1/4
)
update time algorithm by Hen-
zinger, Forster and Nanongkai [
43
], and the randomized algorithm
for decremental graphs by by Chuzhoy and Khanna [
27
] which has
update time
𝑛
2+𝑜 (1)
and which even more recently derandomized
[
26
]. However, the latter algorithm works only in the restricted
setting of vertex deletions and requires 𝑛
1+𝑜 (1)
query time.
Our second contribution includes several new ne-grained lower
bounds for the partially dynamic SSSP and
𝑠
-
𝑡
-SP problems in un-
weighted undirected graphs. The only known conditional lower
bounds for partially dynamic SSSP and
𝑠
-
𝑡
-SP in unweighted graphs
give an update time lower bound of
𝑚
0.5−𝑜 (1)
. While the ES-tree
data structure does achieve an
𝑂 (
√
𝑚)
amortized update/query
time upper bound whenever
𝑚 = Θ(𝑛
2
)
, this upper bound does not
improve for lower sparsities. This motivates the following question:
Is partially dynamic SSSP solvable with amortized update/query time
𝑂 (
√
𝑚) for all sparsities 𝑚?
Our work answers this question with the tools of ne-grained
complexity. Our rst result is based on the following
𝑘
-Cycle hy-
pothesis (see [11, 48]).
Hypothesis 1.2
(
𝑘
-Cycle Hypothesis)
.
In the word-RAM model
with
𝑂 (log𝑚)
bit words, for any constant
𝜖 >
0, there exists a constant
integer
𝑘
, so that there is no
𝑂 (𝑚
2−𝜖
)
time algorithm that can detect
a 𝑘-cycle in an 𝑚-edge graph.
Our rst result says that under the
𝑘
-Cycle Hypothesis, if the
preprocessing time of a partially dynamic
𝑠
-
𝑡
-SP algorithm is sub-
quadratic
𝑂 (𝑚
2−𝜖
)
for
𝜖 >
0, then in fact the algorithm cannot
achieve truly sublinear,
𝑂 (𝑚
1−𝜖
′
)
amortized update and query time
for any
𝜖
′
>
0. This is a quadratic improvement over the previous
known lower bounds, and it is also tight, as trivial recomputation
achieves amortized update/query time 𝑂 (𝑚).
Theorem 1.3. Under Hypothesis 1.2, there can be no constant
𝜖 >
0
such that partially dynamic
𝑠
-
𝑡
SP in undirected graphs can be solved
with
𝑂 (𝑚
2−𝜖
)
preprocessing time, and
𝑂 (𝑚
1−𝜖
)
update and query
time, for all graph sparsities 𝑚.
A consequence of the proof of Theorem 1.3 above is that (under
Hypothesis 1.2) the
𝑂 (𝑚𝑛)
total update time achieved by ES-trees
is essentially optimal, also when
𝑚
is close to linear in
𝑛
. Recall
that the OMv lower bound only showed this for
𝑚 = Θ(𝑛
2
)
. While
the above lower bound is tight, it only holds for truly subquadratic
preprocessing time. Recall that the only known lower bound for
arbitrary polynomial preprocessing time is the
𝑚
0.5−𝑜 (1)
bound
under OMv.
We rst develop an intricate reduction that shows that an ef-
cient enough partially dynamic
𝑠
-
𝑡
SP algorithm can be used to
solve the 4-Clique problem. Then we dene an online version of
4-Clique, similar to OMv that is plausibly hard even for arbitrary
polynomial time preprocessing. We show that if 4-Clique requires
𝑛
𝑐−𝑜 (1)
time for some
𝑐
, then any algorithm for partially dynamic
𝑠
-
𝑡
SP with
𝑂 (𝑚
𝑐/2−𝜖
)
preprocessing time for some
𝜖 >
0, must have
update or query time at least
𝑚
(𝑐−2)/2−𝑜 (1)
. 4-Clique is known to
be solvable in
𝑂 (𝑛
3.252
)
time [
33
], and if the matrix multiplication
exponent
𝜔
is
>
2, the best running time for 4-clique would still be
truly supercubic. Thus, the update time in our conditional lower
bound,
𝑚
(𝑐−2)/2−𝑜 (1)
is polynomially better than
𝑚
0.5−𝑜 (1)
, as long
as
𝜔 >
2. Recent results [
4
,
5
] show that the known techniques for
matrix multiplication cannot show that 𝜔 is less than 2.16.
While the connection between clique detection and
𝑠
-
𝑡
SP is
interesting in its own right, it does not resolve the limitation on
the preprocessing time of our previous lower bound. To x this,
we introduce an online version of 4-Clique, generalizing the OMv
(actually the related OuMv [44]) problem:
Denition 1.4
(OMv3 problem)
.
In the OMv3 problem, we are given
an
𝑛 ×𝑛
Boolean matrix
𝐴
that can be preprocessed and then
𝑛
queries
consisting of three length
𝑛
Boolean vectors
𝑢, 𝑣, 𝑤
have to be answered
online by outputting the Boolean value
Ü
𝑖,𝑗,𝑘
(𝑢
𝑖
∧𝑣
𝑗
∧𝑤
𝑘
∧𝐴[𝑖, 𝑗] ∧𝐴[𝑗, 𝑘] ∧𝐴[𝑘, 𝑖]).
One can think of
𝑢, 𝑣, 𝑤
as giving the neighbors of an incom-
ing vertex
𝑞
in the three partitions of a tripartite graph, and then
the Boolean value just answers whether
𝑞
would be part of a 4-
Clique if it were added to the graph. This is the natural extension of
Henzinger et al.’s OuMv problem. OMv3 is easy to solve in
𝑂 (𝑛
𝜔
)
time per query by computing whether the neighborhood dened
by
𝑢, 𝑣, 𝑤
contains a triangle. We hypothesize that there is no bet-
ter algorithm, even if one is to preprocess the matrix in arbitrary
polynomial time:
Hypothesis 1.5
(OMv3 Hypothesis)
.
Any algorithm solving OMv3
with polynomial preprocessing time needs
𝑛
𝜔+1−𝑜 (1)
total time to
solve OMv3 in the word-RAM model with 𝑂 (log 𝑛) bit words.
Using this Hypothesis, using essentially the same reduction
as from 4-Clique to
𝑠
-
𝑡
SP, we obtain plausible conditional lower
155