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

DOI10.1145/3218657MaRDI QIDQ4625657zbMATH OpenOpenAlexFDO

Authors Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date 25 February 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.08148

zbMATH Keywords

approximate shortest pathshop sets

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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+epsilon)$-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+epsilon)$-approximation algorithm with $m^{1+o(1)}$ expected total update time, thus obtaining near-linear time. Moreover, we obtain $m^{1+o(1)}logW$ 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 $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,epsilon)$-hop set introduced by Cohen [JACM 2000] in the PRAM literature. An $(h,epsilon)$-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+epsilon)$-approximated by their $h$-hop distance (given by a path containing at most $h$ edges) on $G^{\prime }=(V,EcupF)$. Our algorithm can maintain an $(n^{o(1)},epsilon)$-hop set of near-linear size in near-linear time under edge deletions.

Recommendations

• A subquadratic-time algorithm for decremental single-source shortest paths
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• New algorithms and hardness for incremental single-source shortest paths in directed graphs
• Decremental all-pairs shortest paths in deterministic near-linear time
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• Deterministic partially dynamic single source shortest paths for sparse graphs
• A single-source shortest path algorithm for dynamic graphs

Cited in

(22)

• Fast approximate shortest paths in the congested clique
• Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
• Deterministic partially dynamic single source shortest paths for sparse graphs
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Decremental strongly connected components and single-source reachability in near-linear time
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• New algorithms and hardness for incremental single-source shortest paths in directed graphs
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• Hopsets with constant hopbound, and applications to approximate shortest paths
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• A subquadratic-time algorithm for decremental single-source shortest paths
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Deterministic incremental APSP with polylogarithmic update time and stretch
• New tradeoffs for decremental approximate all-pairs shortest paths
• On the size overhead of pairwise spanners
• A unified framework for hopsets
• Bootstrapping dynamic apsp via sparsification

This page was built for publication: Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4625657)