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+ ε ) ( 2 + ϵ ) -APSP with total update time Õ(m1/2n3/2) O ~ ( m 1 / 2 n 3 / 2 ) (when m= n¹⁺ᶜ m = n 1 + c for any constant $$0 0 < c < 1 ). Our second result is $$(2+ε , Wu,v)$$ ( 2 + ϵ , W u , v ) -APSP with total update time $$Õ(nm3/4)$$ O ~ ( n m 3 / 4 ) , where the second term is an additive stretch with respect to $$Wu,v$$ 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 $$Õ(mn)$$ O ~ ( m n ) update time for $$(1+ε )$$ ( 1 + ϵ ) -APSP (Bernstein [11], SICOMP 2016). Our third result is $$(2+ ε )$$ (