Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak · 2024
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 n2-Ω(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.