Dynamic Deterministic Constant-Approximate Distance Oracles with n ε Worst-Case Update Time

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph G = (V, E) with $n$ vertices undergoing both edge insertions and deletions, and an arbitrary parameter $\epsilon\in[1/\log^{c}n, 1$ where $c$ > 0 is a small constant, we can deterministically maintain a data structure with $O(n^{\epsilon})$ worst-case update time that, given any pair of vertices (u, v), returns a $2^{\text{poly}(1/\epsilon)}$ -approximate distance between $u$ and $v$ in poly(1/E) log log $n$ query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a o( $n$ )-approximation while also achieving an n 2-Ω(1) update and $n^{o(1)}$ query time, while our algorithm offers a constant $O_{\epsilon}(1)$ -approximation with $O(n^{\epsilon})$ update time and $o_{\epsilon}$ (log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with $n^{1-\Omega(1)}$ update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approxi- mation of (log log $n)^{2^{O (1 / \epsilon^3)}}$ with amortized update time of $O(n^{\epsilon)}$ and query time of $2^{\mathrm{p}\circ 1\mathrm{y}(1/\epsilon)}\log n$ log log n. We obtain the result by dynamizing tools related to length- constrained expanders [Haeupler-Racke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, FOCS 2024]. Our technique com- pletely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.

Authors

• Bernhard Haeupler
• Yaowei Long
• Thatchaphol Saranurak

Keywords

• Computer science
• Heuristic algorithms
• Data structures
• Deterministic
• Update Time
• Worst-case Time
• Distance Oracle
• Data Structure
• Dynamic Algorithm
• Dynamic Setting
• Small Constant
• Approximate Distance
• Query Time
• Key Step
• Functional Integrity
• Estimation Algorithm
• Shortest Path
• Edge Length
• Local Algorithm
• Maximum Flow
• Local Flow
• Flow Problem
• Constant Approximation
• Small Overhead
• Unit Demand
• Similar Trade-offs
• Standard Reduction
• Independent Work
• Graph algorithms
• Dynamic algorithms
• Distance Oracles