New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

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+\epsilon )$-APSP with total update time $\tilde{O}(m^{1\mathrm{/}2}{n}^{3\mathrm{/}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+\epsilon )$-APSP [Bernstein, SICOMP 2016]. Our second result is $(2+\epsilon ,W_{u,v})$-APSP with total update time $\tilde{O}(n{m}^{3\mathrm{/}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+\epsilon )$-APSP for unweighted graphs in $\tilde{O}(m^{7\mathrm{/}4})$ update time, which for sparse graphs ($m=o(n^{8\mathrm{/}7})$) is the first subquadratic $(2+\epsilon )$-approximation. Our last result for unweighted graphs is $(1+\epsilon ,2(k-1))$-APSP, for $k\ge 2$, with $\tilde{O}(n^{2-1\mathrm{/}k}{m}^{1\mathrm{/}k})$ total update time (when $m=n^{1+c}$ for any constant $c>0$). For comparison, in the special case of $(1+\epsilon ,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.