Fast Deterministic Fully Dynamic Distance Approximation
share
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 < ϵ≤ 1, maintain (1+ϵ)-approximations of the st distance of a single pair of nodes, 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 single-source distances with worst-case update time O(n^1.529) (for the current best known bound on the matrix multiplication coefficient ω). This matches a conditional lower bound by [BNS, FOCS 2019]. We further show that we can go beyond this SSSP bound for the problem of maintaining approximate st distances by providing a deterministic algorithm with worst-case update time O(n^1.447). This even improves upon the fastest known randomized algorithm for this problem. 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 improvements for randomized approximate diameter maintenance.
READ FULL TEXT