Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

Abstract

In the decremental $(1+\epsilon )$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n=|V|,m=|E|$, undergoing edge deletions, and a distinguished source $s\in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates ${\widetilde{\mathbf{dist}}}_G(s,v)$ for each $v\in V$, at any stage, such that ${\mathbf{dist}}_G(s,v)\le {\widetilde{\mathbf{dist}}}_G(s,v)\le (1+\epsilon ){\mathbf{dist}}_G(s,v)$. In the decremental $(1+\epsilon )$-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates ${\widetilde{\mathbf{dist}}}_G(u,v)$ for every $u,v\in V$. In this article, we consider the problems for undirected, unweighted graphs. We present a new \emph{deterministic} algorithm for the decremental $(1+\epsilon )$-approximate SSSP problem that takes total update time $O(m{n}^{0.5+o(1)})$. Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $\tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $\tilde{O}(n^{1.25}\sqrt{m})$ [SODA 2017] whenever $m=O(n^{1.5-o(1)})$. In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic \emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+\epsilon )$-approximate APSP problem with near-optimal total running time $\tilde{O}(mn/\epsilon )$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].

Appeared in SODA'20

References in corpus (9)

• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Dynamic Decremental Approximate Distance Oracles with $(1+\epsilon ,2)$ stretch
• Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
• Diameter Spanners, Eccentricity Spanners, and Approximating Extremal Distances
• Constructing Light Spanners Deterministically in Near-Linear Time

Cited by in corpus (2)

• Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
• Splay Top Trees