2025/11/06 by Jin, Ce, Kirkpatrick, Yael, Stawarz, Michał +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2511.04775
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(n2.259) time [Dürr, IPL 2023; Deng, Kirkpatrick, Rong, Vassilevska Williams, and Zhong, ICALP 2022]. We give an improved algorithm in O(n2.2255) time. For +4 and +6-approximate APSP, we achieve time complexities O(n2.1462) and O(n2.1026) respectively, improving the previous O(n2.155) and O(n2.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.