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 Õ(m¹/²n³/²) (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 Õ(mn) update time for (1 + ϵ)-APSP [Bernstein, SICOMP 2016]. Our second result is (2 + ϵ, Wu,v)-APSP with total update time Õ(nm³/⁴), where the second term is an additive stretch with respect to Wu,v, the maximum weight on the shortest path from u to v. Our third result is (2 + ϵ)-APSP for unweighted graphs in Õ(m⁷/⁴) update time, which for sparse graphs (m = o(n⁸/⁷)) is the first subquadratic (2 + ϵ)-approximation. Our last result for unweighted graphs is (1 + ϵ, 2(k − 1))-APSP, for k ≥ 2, with Õ(n^2−1/km^1/k) total update time (when m = n¹⁺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 Õ(n^2.5). All of our results are randomized, work against an oblivious adversary, and have constant query time.