Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths

Dynamic all-pairs shortest paths is a well-studied problem in the field of dynamic graph algorithms. More specifically, given a directed weighted graph G = (V, E, ω) on n vertices which undergoes a sequence of vertex or edge updates, the goal is to maintain distances between any pair of vertices in V. In a classical work by [Demetrscu and Italiano, 2004], the authors showed that all-pairs shortest paths can be maintained deterministically in amortized Õ(n2) time1, which is nearly optimal. For worst-case update time guarantees, so far the best randomized algorithm has Õ(n3-1/3) time [Abraham, Chechik, Krinninger, 2017], and the best deterministic algorithm needs Õ(n3-2/7) time [Probst Gutenberg, Wulff-Nilsen, 2020]. We provide a faster deterministic worst-case update time of Õ(n3-20/61) for fully dynamic all-pairs shortest paths. To achieve this improvement, we study a natural variant of this problem where a hop constraint is imposed on shortest paths between vertices; that is, given a parameter h, the h-hop shortest path between any pair of vertices s,t ∈ V is a path from s to t with at most h edges whose total weight is minimized. As a result which might be of independent interest, we give a deterministic algorithm that maintains all-pairs h-hop shortest paths under vertex deletions in total update time Õ(n3h + Kn2n2), where K bounds the total number of vertex deletions. * This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV). 1 Õ(·) hides poly-log factors.