TY - GEN
T1 - Fast Deterministic Fully Dynamic Distance Approximation
AU - Brand, Jan Van Den
AU - Forster, Sebastian
AU - Nazari, Yasamin
PY - 2022
Y1 - 2022
N2 - 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 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.
AB - 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 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.
UR - https://www.scopus.com/pages/publications/85142724430
U2 - 10.1109/FOCS54457.2022.00099
DO - 10.1109/FOCS54457.2022.00099
M3 - Conference contribution
SN - 9781665455206
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1011
EP - 1022
BT - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE Computer Society
T2 - 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Y2 - 31 October 2022 through 3 November 2022
ER -