Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

In the decremental single-source shortest paths (SSSP) problem we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [JACM 1981] has been the fastest known algorithm for three decades. At the cost of a (1+ε)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [SODA 2011]. In this paper, we bring the running time down to near-linear: We give a (1+ε)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(m n) time is the m n0.9 + o(1)-time algorithm by Henzinger et al. [STOC 2014, ICALP 2015] which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ε)-hop set introduced by Cohen [JACM 2000] in the PRAM literature. An (h, ε)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ε)-approximated by their h-hop distance (given by a path containing at most h edges) on G'=(V, Ecup F). Our algorithm can maintain an (no(1), ε)-hop set of near-linear size in near-linear time under edge deletions.