# New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Preprint · Michal Dory, Sebastian Forster, Yasamin Nazari, Tijn de Vos

- Archive id: arxiv:2211.01152
- Published: 2022-11-02
- arXiv: https://arxiv.org/abs/2211.01152
- Source URL: https://arxiv.org/abs/2211.01152
- PDF: https://arxiv.org/pdf/2211.01152
- Provenance: arxiv

## Abstract

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with $m$ edges and $n$ nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is $(2+ ε)$-APSP with total update time $\\tilde{O}(m^{1/2}n^{3/2})$ (when $m= n^{1+c}$ for any constant $0\<c\<1$). Prior to our work the fastest algorithm for weighted graphs with approximation at most $3$ had total $\\tilde O(mn)$ update time for $(1+ε)$-APSP \[Bernstein, SICOMP 2016\]. Our second result is $(2+ε, W\_{u,v})$-APSP with total update time $\\tilde{O}(nm^{3/4})$, where the second term is an additive stretch with respect to $W\_{u,v}$, the maximum weight on the shortest path from $u$ to $v$. Our third result is $(2+ ε)$-APSP for unweighted graphs in $\\tilde O(m^{7/4})$ update time, which for sparse graphs ($m=o(n^{8/7})$) is the first subquadratic $(2+ε)$-approximation. Our last result for unweighted graphs is $(1+ε, 2(k-1))$-APSP, for $k \\geq 2 $, with $\\tilde{O}(n^{2-1/k}m^{1/k})$ total update time (when $m=n^{1+c}$ for any constant $c \>0$). For comparison, in the special case of $(1+ε, 2)$-approximation, this improves over the state-of-the-art algorithm by \[Henzinger, Krinninger, Nanongkai, SICOMP 2016\] with total update time of $\\tilde{O}(n^{2.5})$. All of our results are randomized, work against an oblivious adversary, and have constant query time.

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