---
_id: '11855'
abstract:
- lang: eng
text: '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.'
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest
paths on undirected graphs in near-linear total update time. In: *55th Annual
Symposium on Foundations of Computer Science*. Institute of Electrical and
Electronics Engineers; 2014:146-155. doi:10.1109/focs.2014.24'
apa: 'Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2014). Decremental
single-source shortest paths on undirected graphs in near-linear total update
time. In *55th Annual Symposium on Foundations of Computer Science* (pp.
146–155). Philadelphia, PA, United States: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/focs.2014.24'
chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental
Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update
Time.” In *55th Annual Symposium on Foundations of Computer Science*, 146–55.
Institute of Electrical and Electronics Engineers, 2014. https://doi.org/10.1109/focs.2014.24.
ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source
shortest paths on undirected graphs in near-linear total update time,” in *55th
Annual Symposium on Foundations of Computer Science*, Philadelphia, PA, United
States, 2014, pp. 146–155.
ista: '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.'
mla: Henzinger, Monika H., et al. “Decremental Single-Source Shortest Paths on Undirected
Graphs in near-Linear Total Update Time.” *55th Annual Symposium on Foundations
of Computer Science*, Institute of Electrical and Electronics Engineers, 2014,
pp. 146–55, doi:10.1109/focs.2014.24.
short: 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.
conference:
end_date: 2014-10-21
location: Philadelphia, PA, United States
name: 'FOCS: Annual Symposium on Foundations of Computer Science'
start_date: 2014-10-18
date_created: 2022-08-16T08:14:33Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2023-02-21T16:27:34Z
day: '01'
doi: 10.1109/focs.2014.24
extern: '1'
external_id:
arxiv:
- '1402.0054'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1402.0054
month: '10'
oa: 1
oa_version: Preprint
page: 146-155
publication: 55th Annual Symposium on Foundations of Computer Science
publication_identifier:
eisbn:
- 978-1-4799-6517-5
issn:
- 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
record:
- id: '11768'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Decremental single-source shortest paths on undirected graphs in near-linear
total update time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...