Logo der Universität Wien

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


The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. It is one of the most important problems with many potential applications. While its static counterpart can be easily solved in 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 stood the best for three decades, until it was recently improved to O(n^{2+o(1)}) by a (1+ε)-approximation algorithm of Bernstein and Roditty (SODA 2011), and more recently to O(n^{1.8+o(1)}+m^{1+o(1)}) by us (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1+ε)-approximation algorithm with O(m^{1+o(1)}) total update time, thus obtaining near-linear time. Moreover, we obtain O(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(mnlog W) time is our O(mn^{0.986}log W)-time result from STOC 2014 which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, ε)-hop set of a graph G=(V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1+ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E ∪ E'). Our algorithm can maintain an (n^{o(1)}, ε)-hop set of near-linear size in near-linear time. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining our previous monotone Even-Shiloach tree (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest.

Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)
Theory and Applications of Algorithms
Theoretische Informatik
Event Location
Philadelphia, USA
Event Type
Event Dates
October 18-21, 2014
October 2014
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna