Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Authors:
Open Access
- 19 November 2018
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 65 (6) , 1-40
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 [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n 2+ o (1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-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 mn 0.9 + o (1) -time algorithm by Henzinger et al. [18, 19], 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 [12] 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 , E ∪ F ). Our algorithm can maintain an ( n o (1) , ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.Keywords
Funding Information
- European Research Council (340506, 317532)
- Ministry of Education - Singapore (MOE2010-T2-2-082, MOE2012-T1-001-094)
- Nanyang Technological University (317532)
- Austrian Science Fund (P23499-N23)
- Universität Wien (IK I049-N)
This publication has 24 references indexed in Scilit:
- Efficient distributed approximation algorithms via probabilistic tree embeddingsDistributed Computing, 2012
- Dynamic Approximate All-Pairs Shortest Paths in Undirected GraphsSIAM Journal on Computing, 2012
- Improved Dynamic Reachability Algorithms for Directed GraphsSIAM Journal on Computing, 2008
- Approximate distance oraclesJournal of the ACM, 2005
- All pairs shortest paths using bridging sets and rectangular matrix multiplicationJournal of the ACM, 2002
- Polylog-time and near-linear work approximation scheme for undirected shortest pathsJournal of the ACM, 2000
- Undirected single-source shortest paths with positive integer weights in linear timeJournal of the ACM, 1999
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch tSIAM Journal on Computing, 1998
- A Randomized Parallel Algorithm for Single-Source Shortest PathsJournal of Algorithms, 1997
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981