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 < ε\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(n^{1.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(n^{1.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(n^{1.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.

No reviews yet.

No comments yet.