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 ε where 1/logᶜ n<ε<1 and $c>0$ is a small constant, we can deterministically maintain a data structure with nε worst-case update time that, given any pair of vertices $(u,v)$, returns a 2^ poly(1/ε)-approximate distance between u and v in poly(1/ε)loglog 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ᵒ⁽¹⁾ query time, while our algorithm offers a constant Oε(1)-approximation with nε update time and Oε(log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with n1-Ω(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 approximation of (loglog n)^2^O(1/ε³) with amortized update time of nε and query time of 2^ poly(1/ε)log nloglog n. We obtain the result by dynamizing tools related to length-constrained expanders [Haeupler-R\"acke-Ghaffari, STOC 2022; Haeupler-Hershkowitz-Tan, 2023; Haeupler-Huebotter-Ghaffari, 2022]. Our technique completely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.