# Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler

arXiv: https://arxiv.org/abs/2001.10809 · HTML: https://mlsanity.com/paper/2001.10809/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2020.

## Built on by (most cited first, 3 of 3)

- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)

## Abstract (arXiv)

In the decremental (1+ε)-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 ∈ V, and we are asked to process edge deletions efficiently and answer queries for distance estimates widetildedistG(s,v) for each v ∈ V, at any stage, such that distG(s,v) ≤ widetildedistG(s,v) ≤ (1+ ε)distG(s,v). In the decremental (1+ε)-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates widetildedistG(u,v) for every u,v ∈ V. In this article, we consider the problems for undirected, unweighted graphs. We present a new deterministic algorithm for the decremental (1+ε)-approximate SSSP problem that takes total update time O(mn0.5 + o(1)). Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time tildeO(n2) and the best existing algorithm for sparse graphs with running time tildeO(n1.25√m) [SODA 2017] whenever m = O(n1.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 sparse emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental (1+ε)-approximate APSP problem with near-optimal total running time tildeO(mn /ε) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].