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

Preprint · Maximilian Probst Gutenberg, Christian Wulff-Nilsen

- Archive id: arxiv:2001.10809
- Published: 2020-01-29
- DOI: https://doi.org/10.1137/1.9781611975994.154
- arXiv: https://arxiv.org/abs/2001.10809
- Source URL: https://arxiv.org/abs/2001.10809
- PDF: https://arxiv.org/pdf/2001.10809
- Provenance: arxiv

## Abstract

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 \\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) \\leq \\widetilde{\\mathbf{dist}}\_G(s,v) \\leq (1+ ε)\\mathbf{dist}\_G(s,v)$. In the decremental $(1+ε)$-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+ε)$-approximate SSSP problem that takes total update time $O(mn^{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+ε)$-approximate APSP problem with near-optimal total running time $\\tilde{O}(mn /ε)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai \[FOCS 2013\].

_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.