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 two new approximate decremental APSP algorithms, one for weighted and one for unweighted graphs. Our first result is an algorithm that supports $(2+ \epsilon)$-approximate all-pairs constant-time distance queries with total update time $\tilde{O}(m^{1/2}n^{3/2})$ when $m= O(n^{5/3})$ (and $m= n^{1+c}$ for any constant $c >0$), or $\tilde{O}(mn^{2/3})$ when $m = \Omega(n^{5/3})$. Prior to our work the fastest algorithm for weighted graphs with approximation at most $3$ had total $\tilde O(mn)$ update time providing a $(1+\epsilon)$-approximation [Bernstein, SICOMP 2016]. Our technique also yields a decremental algorithm with total update time $\tilde{O}(nm^{3/4})$ supporting $(2+\epsilon, W_{u,v})$-approximate queries where the second term is an additional additive term and $W_{u,v}$ is the maximum weight on the shortest path from $u$ to $v$. Our second result is a decremental algorithm that given an unweighted graph and a constant integer $k \geq 2 $, supports $(1+\epsilon, 2(k-1))$-approximate queries and has $\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+\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 and work against an oblivious adversary.