# Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time

Preprint · Julia Chuzhoy

- Archive id: arxiv:2109.05621
- Published: 2021-09-12
- arXiv: https://arxiv.org/abs/2109.05621
- Source URL: https://arxiv.org/abs/2109.05621
- PDF: https://arxiv.org/pdf/2109.05621
- Provenance: arxiv

## Abstract

We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an $n$-vertex $m$-edge graph $G$ with non-negative edge lengths, that undergoes a sequence of edge deletions. The goal is to support approximate shortest-path queries: given a pair $x,y$ of vertices of $G$, return a path $P$ connecting $x$ to $y$, whose length is within factor $α$ of the length of the shortest $x$-$y$ path, in time $\\tilde O(\|E(P)\|)$, where $α$ is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems. A long line of work culminated in the algorithm of \[Chechik, FOCS 2018\] with near optimal guarantees for the oblivious-adversary setting. Unfortunately, adaptive-adversary setting is still poorly understood. For unweighted graphs, the algorithm of \[Henzinger, Krinninger and Nanongkai, FOCS '13, SICOMP '16\] achieves a $(1+ε)$-approximation with total update time $\\tilde O(mn/ε)$; the best current total update time of $n^{2.5+O(ε)}$ is achieved by the deterministic algorithm of \[Chuzhoy, Saranurak, SODA'21\], with $2^{O(1/ε)}$-multiplicative and $2^{O(\\log^{3/4}n/ε)}$-additive approximation. To the best of our knowledge, for arbitrary non-negative edge weights, the fastest current adaptive-update algorithm has total update time $O(n^{3}\\log L/ε)$, achieving a $(1+ε)$-approximation. Here, L is the ratio of longest to shortest edge lengths. Our main result is a deterministic algorithm for decremental APSP in undirected edge-weighted graphs, that, for any $Ω(1/\\log\\log m)\\leq ε\< 1$, achieves approximation factor $(\\log m)^{2^{O(1/ε)}}$, with total update time $O\\left (m^{1+O(ε)}\\cdot (\\log m)^{O(1/ε^2)}\\cdot \\log L\\right )$.

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