Near-Optimal Approximate Decremental All Pairs Shortest Paths

In this paper we consider the decremental approximate all-pairs shortest paths (APSP) problem, where given a graph G the goal is to maintain approximate shortest paths between all pairs of nodes in G under a sequence of online adversarial edge deletions. We present a decremental APSP algorithm for undirected weighted graphs with (2 + epsilon)k - 1 stretch, Omicron(mn(1/k broken vertical bar) (0(1)) log (nW)) total update time and O(log log (nW)) query time for a fixed constant epsilon, where W is the maximum edge weight (assuming the minimum edge weight is 1) and k is any integer parameter. This is an exponential improvement both in the stretch and in the query time over previous works.