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

Abstract

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+\epsilon )$-approximation factor, the running time was recently improved to $n^{2+o(1)}$ by Bernstein and Roditty [SODA 2011]. In this paper, we bring the running time down to near-linear: We give a $(1+\epsilon )$-approximation algorithm with $m^{1+o(1)}$ expected total update time, thus obtaining near-linear time. Moreover, we obtain $m^{1+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(mn)$ time is the $m{n}^{0.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,\epsilon )$-hop set introduced by Cohen [JACM 2000] in the PRAM literature. An $(h,\epsilon )$-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+\epsilon )$-approximated by their $h$-hop distance (given by a path containing at most $h$ edges) on $G^{\prime }=(V,E\cup F)$. Our algorithm can maintain an $(n^{o(1)},\epsilon )$-hop set of near-linear size in near-linear time under edge deletions.

Accepted to Journal of the ACM. A preliminary version of this paper was presented at the 55th IEEE Symposium on Foundations of Computer Science (FOCS 2014). Abstract shortened to respect the arXiv limit of 1920 characters

Cited by in corpus (3)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks