Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds

Given a directed weighted graph G = (V, E) undergoing vertex insertions and deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of G. In two breakthrough results, Italiano and Demetrescu [STOC '03] presented an algorithm that requires Õ(n 2 ) amortized update time, and Thorup showed in [STOC '05] that worst-case update time Õ(n 2+3/4 ) can be achieved. In this article, we make substantial progress on the problem. We present the following new results:

• We present the first deterministic data structure that breaks the Õ(n 2+3/4 ) worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to Õ(n 2+5/7 ) = Õ(n 2.71.. ) and to Õ(n 2+3/5 ) = Õ(n 2.6 ) for unweighted graphs.

• We present a simple deterministic algorithm with Õ(n 2+3/4 ) worst-case update time ( Õ(n 2+2/3 ) for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time Õ(n 2+2/3 ) ( Õ(n 2+1/2 ) for unweighted graphs) that works against a nonoblivious adversary. Both data structures require space Õ(n 2 ). These are the first exact dynamic algorithms with truly-subcubic update time and space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP'04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].