On Incremental Approximate Shortest Paths in Directed Graphs

Even in the incremental setting, maintaining exact shortest paths in a weighted digraph is computationally challenging. As proved recently by Saha et al. [44], one cannot even maintain the exact distance between a single fixed source-target pair in an incremental graph within $O(m^{2-ϵ})$ total update time (for any density $m$), i.e., significantly faster than recomputing from scratch. The lower bound is conditional on the Min-Weight 4-Clique Hypothesis (eg. [2, 7, 38]) and holds even in the offline setting, that is, when the update sequence is revealed upfront. A folklore observation is that the all-pairs shortest paths (APSP) matrix can be updated after an edge insertion in $O(n^2)$ time, and hence this yields an incremental APSP data structure with $O(m{n}^2)$ total update time. This is optimal if the $n^2$ distances are to be maintained explicitly.

Non-trivial exact data structures are known for the special case of unweighted digraphs. Single-source shortest paths (SSSP) in unweighted digraphs can be maintained in $O(nm)$ total time [23, 31], whereas APSP can be maintained in $\tilde{O}(n^3)$ total time [6]. Both these bounds are near-optimal if the distances are to be maintained explicitly. There is also an $n^{2-o(1)}$ lower bound for maintaining a single source-target distance in an incremental sparse digraph [26].

The lack of non-trivial approaches for exactly maintaining shortest paths in incremental weighted digraphs motivates studying approximate data structures. For SSSP, the classical ES-tree [23, 31] can be generalized to partially dynamic weighted digraphs with real weights in $[1,W]$ at the cost of $(1+ϵ)$-approximation (where $ϵ=O(1)$) and has $\tilde{O}(mn\log (W))$ total update time (see, e.g., [8, 9]). While quadratic in the general case, the approximate ES-tree is rather flexible and might be set up to run much faster – in $\tilde{O}(mh\log (W))$ total time – if guaranteed that shortest (or short enough) paths from $s$ use at most $h$ hops.

Henzinger, Krinninger and Nanongkai [28, 29] were the first to break through the quadratic bound of the ES-tree polynomially, also in the decremental setting, albeit only against an oblivious adversary. Probst Gutenberg, Vassilevska Williams, and Wein [26] showed the first SSSP data structure designed specifically for the incremental setting against an adaptive adversary, with $\tilde{O}(n^2\log (W))$ total update time. Their data structure is deterministic and near-optimal for dense graphs. Chechik and Zhang [15] showed two data structures for sparse graphs: one deterministic with $\tilde{O}(m^{5/3}\log (W))$ total update time and another Monte Carlo randomized with $\tilde{O}((m{n}^{1/2}+m^{7/5})\log (W))$ total update time, correct w.h.p.³³3With high probability, that is, with probability $1-n^{-c}$ for any desired constant $c\ge 1$. against an adaptive adversary. These two bounds were subsequently improved to $\tilde{O}(m^{3/2}\log (W))$ (deterministic) and $\tilde{O}(m^{4/3}\log (W))$ (randomized) respectively by Kyng, Meierhans and Probst Gutenberg [36].

Very recently, Chen et al. [17] gave a deterministic $(1+ϵ)$-approximate incremental min-cost flow algorithm implying that a $(1+ϵ)$-approximate shortest path for a single source-target pair in a polynomially weighted digraph can be maintained in $m^{1+o(1)}$ time.

No non-trivial conditional lower bounds for incremental approximate SSSP have been described to date and thus the existence of an SSSP data structure with near-linear total update time remains open.

Bernstein [9] showed a Monte Carlo randomized data structure maintaining $(1+ϵ)$-approximate APSP in either incremental or decremental setting with $\tilde{O}(mn\log (W))$ total update time. This bound is near-optimal (even for incremental transitive closure, conditional on the OMv conjecture [30]), but the data structure gives correct answers w.h.p. only against an oblivious adversary. A deterministic $(1+ϵ)$-approximate data structure with $\tilde{O}(n^3\log (W))$ total update time is known [35]. This is near-optimal for dense graphs [29]. Karczmarz and Łącki [34] showed a deterministic data structure with $\tilde{O}(m{n}^{4/3}{\log }^2(W))$ total update time that is more efficient for sparse graphs.

Interestingly, the incremental APSP data structures for sparse digraphs [9, 34] are both obtained without resorting to any of the critical ideas from the state-of-the-art sparse incremental SSSP data structures [36]. Instead, they work by running approximate ES-trees on carefully selected instances where approximately shortest paths from the source have sublinear numbers of hops. Note that a deterministic bound $\tilde{O}(n{m}^{3/2}\log (W))$ and a randomized adaptive bound $\tilde{O}(n{m}^{4/3}\log (W))$ could be achieved by simply employing the two data structures of [36] for all possible sources $s\in V$. This black-box application does not improve upon [34], though. It is thus interesting to ask whether the data structures of [15, 36], just like the ES-tree, could be adjusted to run faster in some special cases that are useful in designing all-pairs data structures.

Finally, we also prove that the $(1+ϵ)$-approximate incremental SSSP problem has a near-linear deterministic offline solution. Formally, we show:

Note that incremental and decremental settings are equivalent in the offline scenario, so the above works for decremental update sequences as well. To the best of our knowledge, no prior⁵⁵5An independent and parallel work [41] established a similar result on offline incremental SSSP. work described offline partially dynamic $(1+ϵ)$-approximate SSSP algorithms. It is worth noting that for dense graphs, the best known online data structures [12, 26] already run in near-optimal $\tilde{O}(n^2\log (W))$ time. However, the state-of-the-art partially dynamic SSSP bounds [12, 36, 26] are still off from near-linear by polynomial factors.

Theorem 3 implies that if incremental or decremental approximate SSSP happen to not have near-linear algorithms, then showing a (conditional) lower bound for the problem requires exploiting the online nature of the problem. For example, showing reductions from such problems as the Min-Weight $k$-Clique or $k$-cycle detection (as used in [44] and [26], respectively, for exact shortest path) cannot yield non-trivial lower bounds for partially dynamic SSSP.

Offline incremental APSP and its special cases have been studied before under the name all-pairs shortest paths for all flows (APSP-AF) [22, 45], or – in a special case when edges are inserted sorted by their weights – all-pairs bounded-leg shortest paths (APBLSP) [13, 21, 42]. For polynomially weighted digraphs, all known non-trivial data structures are $(1+ϵ)$-approximate. Duan and Ren [22] described a deterministic data structure with $\tilde{O}(n^{(\omega +3)/2}\log (W))$ preprocessing and $O(\log \log (nW))$ query time.⁶⁶6Here, $\omega$ denotes the matrix multiplication exponent. Currently, it is known that $\omega \le 2.372$ [3]. For sparser graphs with polynomial weights, the randomized partially dynamic data structure of [9] (augmented with persistence [20] to enable answering queries about individual graph versions) has $\tilde{O}(mn)$ total update time and remains the state of the art, also for APBLSP. By applying Theorem 3 for each source, one obtains an APSP-AF data structure that is much simpler, deterministic, and a log-factor faster than [9].

Finally, let us remark that even though, as presented in this paper, all the data structures we develop only maintain or output distance estimates, they can be easily extended to enable reporting a requested approximately shortest path $P$ in near-optimal $\tilde{O}(|P|)$ time.

Note that the vertices $C_0\cup \mathrm{\dots }\cup C_{k-1}$ are $(k-1)$-certified. As a result, by Lemma 12, after running $\text{Propagate}(C_k\cup \mathrm{\dots }\cup C_r)$, we have that vertices $V_{\mathrm{touched}}$ are $k$-certified and thus can be assigned ranks $k$. By Observation 11, there is no need to change the ranks of $V\setminus V_{\mathrm{touched}}$. $◀$

When Synchronize completes, we have

for all $k\in \{0,\mathrm{\dots },r\}$. We will show by induction that $C_{r-i}\ge 2^i$ for all $i=0,\mathrm{\dots },r$. For $i=0$, we have $C_r\ge 0$ trivially. For $i\ge 1$, by (1) applied to $k=r-i$ and the inductive assumption we get:

so $\mathrm{deg}(C_{r-i})\ge 2^i$, finishing the proof. Note that for $i=r$, we get $\mathrm{deg}(C_0)\ge 2^r$ and since $\mathrm{deg}(C_0)\le m$, we get $2^r\le m$. $◀$

Observation 13 and Lemma 14 show that by using synchronization, the ranks of the vertices will be correct and will be kept bounded by ${\log }_{2}m$.

For $t=s$, the lemma is trivial since $d(s)=0$ holds always. Let $t\ne s$. Consider any simple shortest path $P$ from $s$ to $t$ and let $u\in V$ be the second vertex on $P$. We have $P=e\cdot P^{\prime }$, where $e=su$, $P^{\prime }=u\to v$ and $P^{\prime }\subseteq G[V\setminus \{s\}]$. By Invariant 4, we have $d(u)\le (1+\xi )(d(s)+w(e))$. By the definition of $rank(u)$, we have $d(t)\le {(1+\xi )}^{rank(u)}\cdot (d(u)+w(P^{\prime }))$. As $rank(u)\le r$, we get:

Finally, ${(1+\xi )}^{r+1}\cdot \mathrm{dist}(s,t)\le {(1+\xi )}^{1+{\log }_{2}m}\cdot \mathrm{dist}(s,t)$ follows from Lemma 14. $◀$

First of all, observe that all edge updates that do not immediately decrease some estimate by a factor of at least $1+\xi$ are processed in constant time. The total cost of processing such updates is hence $O(\mathrm{\Delta })$.

It is easy to see that, apart from the above, the running time is dominated by the total time of the $\text{Propagate}$ calls. In fact, the total update time can be (coarsely) bounded by summing the degrees of the vertices that are pushed to the queue $Q$ in $\text{Propagate}$. Similarly as in Section 3, we can bound the total cost incurred by pushing a vertex after its estimate drops by

Note that the only other way a vertex $v$ can be pushed to the queue in $Q$ (without a drop in the estimate $d(v)$) is if $v$ is in the input set of the $\text{Propagate}$ call inside Synchronize. Thus, consider some call $\text{Propagate}(C_k\cup C_{k+1}\mathrm{\cdots }\cup C_r)$ inside Synchronize for $k\in \{0,\mathrm{\dots },r\}$ such that $\mathrm{deg}(C_k)\le \mathrm{deg}(C_{k+1})+\mathrm{\cdots }+\mathrm{deg}(C_r)$. Observe that in such a case we can bound the cost of processing the vertices initially pushed to the queue $Q$ by $O(\log n)$ times

Recall that after such a $\text{Propagate}$ call completes, the ranks of all vertices $C_{k+1}\cup \mathrm{\dots }\cup C_r$ drop by at least $1$. We can thus bound the total sum of expressions $\mathrm{deg}(C_{k+1})+\mathrm{\dots }+\mathrm{deg}(C_r)$ throughout by $m$ times the maximum number of times some vertex $v$ may have its rank increased. However, note that the rank of a vertex $v$ can only increase if $v\in V_{\mathrm{touched}}$ in line 5 of Algorithm 2. But the presence of $v$ in $V_{\mathrm{touched}}$ in that case is caused by $d(v)$ dropping by a factor of at least $1+\xi$. We conclude that $rank(v)$ may only increase $O(\mathrm{\ell })$ times. As a result, the total cost $\text{Propagate}$ calls in Synchronize can also be bounded by $O(m\mathrm{\ell }\log n)=O(m\log (nW)\log (n)/\xi )$.

The above analysis combined with Lemma 15 yields Theorem 8.

Recall from Lemma 6 that running $\text{Propagate}(V)$ makes all vertices $0$-certified. As a result, by running $\text{Propagate}(V)$ and subsequently setting all vertex ranks and the rank offset $\rho$ to $0$, in $O(m+n\log n)$ time we can get rid of the pathwise error of the maintained estimates $d(\cdot )$.

Note that in the running time analysis so far, the work performed inside Synchronize was fully charged to the unit rank increases that made the ranks of the $\text{Propagate}$’s input vertices positive. Consequently, as the discussed reset procedure zeroes out ranks, invoking it any number of times interleaved with the other discussed operations does not increase the total update time bound of the other operations of the data structure.

Reducing the vertex certificates all the way down to $0$ might be unnecessary; keeping the certificates bounded might be just enough. In the full version, we discuss the randomized approach of [15] used to achieve that (adapted to our needs) and prove the following theorem.