# A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths

Preprint · Julia Chuzhoy, Ruimin Zhang

- Archive id: arxiv:2304.09321
- Published: 2023-04-18
- arXiv: https://arxiv.org/abs/2304.09321
- Source URL: https://arxiv.org/abs/2304.09321
- PDF: https://arxiv.org/pdf/2304.09321
- Provenance: arxiv

## Abstract

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an $n$-vertex graph $G$ with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter $ε$, achieves approximation factor $(\\log\\log n)^{2^{O(1/ε^3)}}$, and has amortized update time $O(n^ε\\log L)$ per operation, where $L$ is the ratio of longest to shortest edge length. Query time for distance-query is $O(2^{O(1/ε)}\\cdot \\log n\\cdot \\log\\log L)$, and query time for shortest-path query is $O(\|E(P)\|+2^{O(1/ε)}\\cdot \\log n\\cdot \\log\\log L)$, where $P$ is the path that the algorithm returns. To the best of our knowledge, even allowing any $o(n)$-approximation factor, no adaptive-update algorithms with better than $Θ(m)$ amortized update time and better than $Θ(n)$ query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.

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