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

06/05/2023
by   Xiao Mao, et al.
0

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 amortized algorithm with Õ(n ^ 2) update-time 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 improvement is made possible using a novel multi-layer approach that exploits the gaps between hops (number of vertices traversed) of paths.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset