conference paper
Decremental single-source shortest paths on undirected graphs in near-linear total update time
published
yes
Monika H
Henzinger
author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530
Sebastian
Krinninger
author
Danupon
Nanongkai
author
FOCS: Annual Symposium on Foundations of Computer Science
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. While its static counterpart can be easily 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. With the loss of a (1 + ε)-approximation factor, the running time was recently improved to O(n 2+o(1) ) by Bernstein and Roditty (SODA 2011), and more recently to O(n 1.8+o(1) + m 1+o(1) ) by Henzinger, Krinninger, and Nanongkai (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(mn log W) time is the O(mn 0.986 log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (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 under edge deletions. 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 the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest.
Institute of Electrical and Electronics Engineers2014Philadelphia, PA, United States
eng
55th Annual Symposium on Foundations of Computer Science
0272-5428
1402.005410.1109/focs.2014.24
146-155
https://research-explorer.ista.ac.at/record/11768
yes
Henzinger, Monika H., et al. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” <i>55th Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2014, pp. 146–55, doi:<a href="https://doi.org/10.1109/focs.2014.24">10.1109/focs.2014.24</a>.
Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: <i>55th Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 2014:146-155. doi:<a href="https://doi.org/10.1109/focs.2014.24">10.1109/focs.2014.24</a>
Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update Time.” In <i>55th Annual Symposium on Foundations of Computer Science</i>, 146–55. Institute of Electrical and Electronics Engineers, 2014. <a href="https://doi.org/10.1109/focs.2014.24">https://doi.org/10.1109/focs.2014.24</a>.
Henzinger MH, Krinninger S, Nanongkai D. 2014. Decremental single-source shortest paths on undirected graphs in near-linear total update time. 55th Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 146–155.
Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2014). Decremental single-source shortest paths on undirected graphs in near-linear total update time. In <i>55th Annual Symposium on Foundations of Computer Science</i> (pp. 146–155). Philadelphia, PA, United States: Institute of Electrical and Electronics Engineers. <a href="https://doi.org/10.1109/focs.2014.24">https://doi.org/10.1109/focs.2014.24</a>
M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” in <i>55th Annual Symposium on Foundations of Computer Science</i>, Philadelphia, PA, United States, 2014, pp. 146–155.
M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, 55th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2014, pp. 146–155.
118552022-08-16T08:14:33Z2023-02-21T16:27:34Z