# Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time

Preprint · Xiao Mao

- Archive id: arxiv:2306.02662
- Published: 2023-06-05
- arXiv: https://arxiv.org/abs/2306.02662
- Source URL: https://arxiv.org/abs/2306.02662
- PDF: https://arxiv.org/pdf/2306.02662
- Provenance: arxiv

## Abstract

The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems in theoretical computer science. It asks to compute the distance matrix of a given $n$-vertex graph. We revisit the classical problem of maintaining the distance matrix under a fully dynamic setting undergoing vertex insertions and deletions with a fast worst-case running time and efficient space usage. Although an algorithm with amortized update-time $\\tilde O(n ^ 2)$ has been known for nearly two decades \[Demetrescu and Italiano, STOC 2003\], the current best algorithm for worst-case running time with efficient space usage runs is due to \[Gutenberg and Wulff-Nilsen, SODA 2020\], which improves the space usage of the previous algorithm due to \[Abraham, Chechik, and Krinninger, SODA 2017\] to $\\tilde O(n ^ 2)$ but fails to improve their running time of $\\tilde O(n ^ {2 + 2 / 3})$. It has been conjectured that no algorithm in $O(n ^ {2.5 - ε})$ worst-case update time exists. For graphs without negative cycles, we meet this conjectured lower bound by introducing a Monte Carlo algorithm running in randomized $\\tilde O(n ^ {2.5})$ time while keeping the $\\tilde O(n ^ 2)$ space bound from the previous algorithm. Our breakthrough is made possible by the idea of \`\`hop-dominant shortest paths,'' which are shortest paths with a constraint on hops (number of vertices) that remain shortest after we relax the constraint by a constant factor.

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