New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Abstract

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with $m$ edges and $n$ nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is $(2+ ε)$-APSP with total update time $\tilde{O}(m^{1/2}n^{3/2})$ (when $m= n^{1+c}$ for any constant $0<c<1$). Prior to our work the fastest algorithm for weighted graphs with approximation at most $3$ had total $\tilde O(mn)$ update time for $(1+ε)$-APSP [Bernstein, SICOMP 2016]. Our second result is $(2+ε, W_{u,v})$-APSP with total update time $\tilde{O}(nm^{3/4})$, where the second term is an additive stretch with respect to $W_{u,v}$, the maximum weight on the shortest path from $u$ to $v$. Our third result is $(2+ ε)$-APSP for unweighted graphs in $\tilde O(m^{7/4})$ update time, which for sparse graphs ($m=o(n^{8/7})$) is the first subquadratic $(2+ε)$-approximation. Our last result for unweighted graphs is $(1+ε, 2(k-1))$-APSP, for $k \geq 2 $, with $\tilde{O}(n^{2-1/k}m^{1/k})$ total update time (when $m=n^{1+c}$ for any constant $c >0$). For comparison, in the special case of $(1+ε, 2)$-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of $\tilde{O}(n^{2.5})$. All of our results are randomized, work against an oblivious adversary, and have constant query time.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.