2023/06/05 by Xiao Mao, Mao, Xiao · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2306.02662
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) 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 ``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.