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

Preprint · Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

- Archive id: arxiv:1512.08148
- Published: 2015-12-26
- DOI: https://doi.org/10.1109/focs.2014.24
- arXiv: https://arxiv.org/abs/1512.08148
- Source URL: https://arxiv.org/abs/1512.08148
- PDF: https://arxiv.org/pdf/1512.08148
- Provenance: arxiv

## 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+ε)$-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+ε)$-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(m n)$ 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, ε)$-hop set introduced by Cohen \[JACM 2000\] 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\\cup F)$. Our algorithm can maintain an $(n^{o(1)}, ε)$-hop set of near-linear size in near-linear time under edge deletions.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.