Key points are not available for this paper at this 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 Õ(n 2) 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 Õ(n 2) but fails to improve their running time of Õ(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 Õ(n 2.5) time while keeping the Õ(n 2) space bound from the previous algorithm. Our breakthrough is made possible by the idea of "hop-dominant 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.
Xiao Mao (Mon,) studied this question.