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(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.

Authors

• Jan van den Brand
• Sebastian Forster
• Yasamin Nazari

Keywords

• Computer science
• Heuristic algorithms
• Maintenance engineering
• Approximation algorithms
• Data structures
• Deterministic
• Data Structure
• Fastest
• Undirected
• Matrix Multiplication
• Pair Of Nodes
• Dynamic Algorithm
• Algebraic Structure
• Update Time
• Approximate Distance
• Worst-case Time
• Unweighted Graph
• Running Time
• Cardinality
• Invertible
• Estimation Algorithm
• Shortest Path
• Reachable
• Set Of Covariates
• Static Algorithm
• Rank Of Matrix
• Submatrix
• Directed Graph
• Dynamic Matrix
• Query Time
• Dynamic Graph
• Preprocessing Time
• Nonzero Entries
• Graph Algorithms