Improved Additive Approximation Algorithms for APSP

The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick [SICOMP'01]. Many recent works have attempted to improve these original algorithms using the algebraic tools of fast matrix multiplication. We improve on these results for the following problems.

For +2-approximate APSP, the state-of-the-art algorithm runs in O(n 2.259 ) time [Dürr, IPL 2023; Deng, Kirkpatrick, Rong, Vassilevska Williams, and Zhong, ICALP 2022]. We give an improved algorithm in O(n 2.2255 ) time.

For +4 and +6-approximate APSP, we achieve time complexities O(n 2.1462 ) and O(n 2.1026 ) respectively, improving the previous O(n 2.155 ) and O(n 2.103 ) achieved by [Saha and Ye, SODA 2024].

In contrast to previous works, we do not use the big hammer of bounded-difference (min, +)product algorithms. Instead, our algorithms are based on a simple technique that decomposes the input graph into a small number of clusters of constant diameter and a remainder of low degree vertices, which could be of independent interest in the study of shortest paths problems. We then use only standard fast matrix multiplication to obtain our improvements.