Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time

The All-Pairs Shortest Paths (APSP) problem is one of the fundamental problems in theoretical computer science. It asks to compute the distance matrix of a given n-vertex graph. We revisit the classical problem of maintaining the distance matrix under a fully dynamic setting undergoing vertex insertions and deletions with a fast worst-case running time and efficient space usage.

Although an algorithm with amortized update-time O(n 2 ) 1 has been known for nearly two decades [Demetrescu and Italiano, STOC 2003], the current best algorithm for worst-case running time with efficient space usage runs is due to [Gutenberg and Wulff-Nilsen, SODA 2020], which improves the space usage of the previous algorithm due to [Abraham, Chechik, and Krinninger, SODA 2017] to O(n 2 ) but fails to improve their running time of O(n 2+2/3 ). It has been conjectured that no algorithm in O(n 2.5-ε ) worst-case update time exists. For graphs without negative cycles, we meet this conjectured lower bound by introducing a Monte Carlo algorithm running in randomized O(n 2.5 ) time while keeping the O(n 2 ) space bound from the previous algorithm. Our breakthrough is made possible by the idea of "hopdominant shortest paths," which are shortest paths with a constraint on hops (number of vertices) that remain shortest after we relax the constraint by a constant factor.

1 Throughout this paper, we use O(f ) to denote O(f • poly log(f )). √ log n) time [Wil14], and thus it has been conjectured that an algorithm running in O(n 3-ε ) time is impossible for any ε > 0. However, under many dynamic settings of the APSP problem where the graph undergoes modifications such as vertex/edge insertion/deletions, the distance matrix can be updated in a faster time than a cubic re-computation from scratch.

The Problem. In this paper, we study the fully dynamic setting under vertex insertion/deletions with a faster worst-case time. Formally, we are given a graph G := V, E with |V | = n that undergoes vertex insertions and deletions where each vertex is inserted/deleted together with its incident edges. Our goal is to minimize the update time, which is the time needed to refresh the distance matrix. Specifically, since APSP without any updates already takes O(n 3 ) time, we allow a preprocessing procedure that takes place before the first update whose running time is not part of the update time since it does not "refresh" the distance matrix. We measure the worst-case update time which is opposed to amortized update time. In the randomized setting, the worst-case update time is a time bound under which every update can finish with the correct answer with a probability of 1n -c for some constant c > 0.

We point out that in the fully dynamic setting, vertex updates are always more general than edge updates since any edge update can be easily simulated by a deletion and a re-insertion of one of the two incident vertices.

Previous Work. Algorithms for dynamic All-Pairs Shortest Path Problem have been known since the 1960s, the earliest partially dynamic algorithm was the well-known Floyd-Warshall Algorithm [Flo62, War62] from as early as 1962 2 that can be easily extended to handle vertex insertion for O(n 2 ) time per update given the distance matrix of the current n-vertex graph. It was not until the end of that century that the first fully dynamic algorithm was given by King [Kin99], with O(n 2.5 √ W log n) amortized update time per edge insertion/deletion where W is the largest edge weight. Their algorithm was based on a classic data structure for decremental Single-Source Shortest Paths by Even and Shiloach [ES81]. Later, King and Thorup [KT01] improved the space bound from O(n 3 ) to O(n 2.5 √ W ). The follow-up work by Demetrescu and Italiano [DI02, DI06] generalized the result to real edge weights from a set of size S. In 2004, a breakthrough by Demetrescu and Italiano [DI04] gave an algorithm with O(n 2 ) amortized update time per vertex insertion/deletion using O(n 3 ) space. Thorup [Tho04] simplified their approach, shaved some logarithmic factors, and extended it to handle negative cycles. Based on his approach, he developed the first fully dynamic algorithm with a better worst-case update time for vertex insertion/deletions than recomputation from scratch with O(n 2+3/4 ) time per update, using a space super-cubic in n. In 2017, Abraham, Chechik and Krinninger [ACK17] improved the space to O(n 3 ) and designed a randomized algorithm with O(n 2+2/3 ) worst-case update time per vertex update against an adaptive adversary. The current state-of-the-art algorithms are by Gutenberg and Wulff-Nilsen in 2020 [GWN20b]. They achieved O(n 2+4/7 ) deterministic update time but failed to improve the randomized update time and instead only managed to improve space usage to O(n 2 ). Interestingly, their algorithm is a Las Vegas algorithm while both our algorithm and Abraham, Chechik