Improved Additive Approximation Algorithms for APSP

Abstract

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.