New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Abstract 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+ \epsilon )$$ ( 2 + ϵ ) -APSP with total update time $$\tilde{O}(m^{1/2}n^{3/2})$$ O ~ ( m 1 / 2 n 3 / 2 ) (when $$m= n^{1+c}$$ m = n 1 + c for any constant $$0 0 < c < 1 ). Our second result is $$(2+\epsilon , W_{u,v})$$ ( 2 + ϵ , W u , v ) -APSP with total update time $$\tilde{O}(nm^{3/4})$$ O ~ ( n m 3 / 4 ) , where the second term is an additive stretch with respect to $$W_{u,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 $$\tilde{O}(mn)$$ O ~ ( m n ) update time for $$(1+\epsilon )$$ ( 1 + ϵ ) -APSP (Bernstein [11], SICOMP 2016). Our third result is $$(2+ \epsilon )$$ (