# Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

Preprint · Maximilian Probst Gutenberg, Christian Wulff-Nilsen

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

## Abstract

Given a directed weighted graph $G=(V,E)$ undergoing vertex insertions \\emph{and} deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of $G$. In two breakthrough results, Italiano and Demetrescu \[STOC '03\] presented an algorithm that requires $\\tilde{O}(n^2)$ \\emph{amortized} update time, and Thorup showed in \[STOC '05\] that \\emph{worst-case} update time $\\tilde{O}(n^{2+3/4})$ can be achieved. In this article, we make substantial progress on the problem. We present the following new results: (1) We present the first deterministic data structure that breaks the $\\tilde{O}(n^{2+3/4})$ worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to $\\tilde{O}(n^{2+5/7}) = \\tilde{O}(n^{2.71..})$ and to $\\tilde{O}(n^{2+3/5}) = \\tilde{O}(n^{2.6})$ for unweighted graphs. (2) We present a simple deterministic algorithm with $\\tilde{O}(n^{2+3/4})$ worst-case update time ($\\tilde{O}(n^{2+2/3})$ for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time $\\tilde{O}(n^{2+2/3})$ ($\\tilde{O}(n^{2 + 1/2})$ for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space $\\tilde{O}(n^2)$. These are the first exact dynamic algorithms with truly-subcubic update time \\emph{and} space usage. This makes significant progress on an open question posed in multiple articles \[COCOON'01, STOC '03, ICALP'04, Encyclopedia of Algorithms '08\] and is critical to algorithms in practice \[TALG '06\] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time \[SODA '17\].

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