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 [Bernstein, SICOMP'16]. Our technique also yields a decremental algorithm with total update time $\tilde{O}(nm^{3/4})$ supporting $(2+\epsilon, W_{u,v})$-approximate queries. 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 by [Henzinger et al., SICOMP'16] with total update time of $\tilde{O}(n^{2.5})$. All of our results are randomized and work against an oblivious adversary. Our approach also leads to a new static distance oracle construction. In particular, we construct a distance oracle in $\tilde O(mn^{2/3})$ time that supports constant time $2$-approximate queries. For sparse graphs, the preprocessing time of the algorithm matches conditional lower bounds [Patrascu et al., FOCS'12; Abboud et al., STOC'23]. To the best of our knowledge, this is the first 2-approximate distance oracle that has subquadratic preprocessing time in sparse graphs.