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+ϵ)$ -APSP with total update time $\tilde{O}\left(m^{1/2}{n}^{3/2}\right)$ (when $m=n^{1+c}$ for any constant $0<c<1$ ). Our second result is $(2+ϵ,W_{u,v})$ -APSP with total update time $\tilde{O}\left(n{m}^{3/4}\right)$ , where the second term is an additive stretch with respect to $W_{u,v}$ , the maximum weight on the current shortest path from u to v. Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total $\tilde{O}\left(mn\right)$ update time for $(1+ϵ)$ -APSP (Bernstein [11], SICOMP 2016). Our third result is $(2+ϵ)$ -APSP for unweighted graphs in $\tilde{O}\left(m^{7/4}\right)$ update time, which for sparse graphs ( $m=o\left(n^{8/7}\right)$ ) is the first subquadratic $(2+ϵ)$ -approximation. Our last result for unweighted graphs is $(1+ϵ,2(k-1\left)\right)$ -APSP, for $k\ge 2$ , with $\tilde{O}\left(n^{2-1/k}{m}^{1/k}\right)$ total update time. For comparison, in the special case of $(1+ϵ,2)$ -approximation, this improves over the state-of-the-art algorithm by Henzinger et al. [2], SICOMP 2016 with total update time of $\tilde{O}\left(n^{2.5}\right)$ . All of our results are randomized, work against an oblivious adversary, and have constant query time.