# Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

Preprint · Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai

- Archive id: arxiv:1308.0776
- Published: 2013-08-04
- Venue: SIAM Journal on Computing 45(3): 947-1006 (2016)
- DOI: https://doi.org/10.1137/140957299
- arXiv: https://arxiv.org/abs/1308.0776
- Source URL: https://arxiv.org/abs/1308.0776
- PDF: https://arxiv.org/pdf/1308.0776
- Provenance: arxiv

## Abstract

We study dynamic $(1+ε)$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of $\\tilde O(mn/ε)$ and constant query time by Roditty and Zwick \[FOCS 2004\]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach \[JACM 1981\]; it has a total update time of $O(mn^2)$ and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of $\\tilde O(n^{5/2}/ε)$ and constant query time that has an additive error of $2$ in addition to the $1+ε$ multiplicative error. This beats the previous $\\tilde O(mn/ε)$ time when $m=Ω(n^{3/2})$. Note that the additive error is unavoidable since, even in the static case, an $O(n^{3-δ})$-time (a so-called truly subcubic) combinatorial algorithm with $1+ε$ multiplicative error cannot have an additive error less than $2-ε$, unless we make a major breakthrough for Boolean matrix multiplication \[Dor et al. FOCS 1996\] and many other long-standing problems \[Vassilevska Williams and Williams FOCS 2010\]. The algorithm can also be turned into a $(2+ε)$-approximation algorithm (without an additive error) with the same time guarantees, improving the recent $(3+ε)$-approximation algorithm with $\\tilde O(n^{5/2+O(\\sqrt{\\log{(1/ε)}/\\log n})})$ running time of Bernstein and Roditty \[SODA 2011\] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of $\\tilde O(mn/ε)$ and a query time of $O(\\log\\log n)$. The algorithm has a multiplicative error of $1+ε$ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein \[STOC 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.