Fast Deterministic Fully Dynamic Distance Approximation

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain improved dynamic algorithms that, given an unweighted and undirected graph G = (V, E) undergoing edge insertions and deletions, and a parameter $0 \lt \epsilon \leq 1$, maintain (1 + ϵ)-approximations of the st-distance between a given pair of nodes s and t, the distances from a single source to all nodes (“SSSP”), the distances from multiple sources to all nodes (“MSSP”), or the distances between all nodes (“APSP”). Our main result is a deterministic algorithm for maintaining (1 + ϵ)-approximate st-distance with worst-case update time O(n1.407) (for the current best known bound on the matrix multiplication exponent (ω). This even improves upon the fastest known randomized algorithm for this problem. Similar to several other well-studied dynamic problems whose state-of-the-art worst-case update time is O(n1.407), this matches a conditional lower bound [BNS, FOCS 2019]. We further give a deterministic algorithm for maintaining (1 + ϵ)-approximate single-source distances with worst-case update time O(n1.529), which also matches a conditional lower bound. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining (1 + ϵ, β)-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improved randomized algorithms for several problems such as exact st-distances and diameter approximation.