Faster Approximate All Pairs Shortest Paths

The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on n vertices, no truly sub-cubic algorithms exist to compute APSP exactly even for undirected graphs. This is popularly known as the APSP conjecture and has played a prominent role in developing the field of fine-grained complexity. The seminal results of Seidel and Zwick show that using fast matrix multiplication (FMM) it is possible to compute APSP on unweighted undirected graphs exactly in Õ(n ω ) time, and can be approximated within (1 + ϵ) factor in weighted undirected graphs in time Õ(n ω ) respectively. Here ω is the exponent of FMM, which currently stands at ω = 2.37188. Moreover even for unweighted undirected graphs, it is not possible to obtain a (2 -ϵ)-multiplicative approximation of APSP for any ϵ > 0 in o(n ω ) time. Since 2000, a result by Dor, Halperin, and Zwick gave the best 2 approximation algorithm for APSP in unweighted undirected graphs in time Õ(n 7/3 ). This result was recently improved by Deng, Kirkpatrick, Rong, Williams and Zhong to Õ(n 2.2593 ) using fast min-plus product for bounded-difference matrices which uses FMM as a subroutine (the stated bound here uses new results for computing such min-plus products by Durr). In fact both these results obtain a +2-additive approximation. Recently, Roditty (STOC, 2023) improved the previous bounds for multiplicative 2-approximation of APSP in unweighted undirected graphs giving the best known bound of Õ(n 2.25 ). All these algorithms are deterministic. Roditty also considers estimating shortest paths for all paths of length ≥ k for k ≥ 4, and gives improved bounds when the underlying graph is sparse using randomization. Though for dense graphs, the best known bounds still remained at those provided by Dor et al. more than two decades back.

In this paper, we provide a multitude of new results for multiplicative and additive approximations of APSP in undirected graphs for both unweighted and weighted cases. We provide new algorithms for multiplicative 2-approximation of unweighted graphs: a deterministic one that runs in Õ(n 2.072 ) time and a randomized one that runs in Õ(n 2.0318 ) on expectation improving upon the best known bound of Õ(n 2.25 ). The algorithm uses FMM as well as new combinatorial insights. For 2-approximating paths of length ≥ k, k ≥ 4, we provide the first improvement after Dor et al. for dense graphs even just using combinatorial methods, and then improve it further using FMM. We next consider additive approximations, and provide improved bounds for all additive β-approximations, β ≥ 4. For example, we achieve a running time of Õ(n 2.155 ) for +4 additive approximation improving over the previously known bound of Õ(n 2.2 ), and for a +6 additive approximation, our algorithm has a running time of Õ(n 2.103 ) as opposed to the Õ(n 2.125 ) time that was previously known. For weighted graphs, we show that by allowing small additive errors along with an (1+ϵ)-multiplicative approximation, it is possible to improve upon Zwick's Õ(n ω ) algorithm. For example, it is possible to obtain a bi-criteria (1 + ϵ, 2w u,v ) approximation in Õ(n 2.152 ) time for the shortest path distance between all vertex pairs u, v where w u,v is the highest weight edge on the u-v shortest path. Additionally, we provide a landscape of such bi-criteria approximations for weighted and unweighted graphs. Our results point out the crucial role that FMM can play even on approximating APSP on unweighted undirected graphs, and reveal new bottlenecks towards achieving a quadratic running time to approximate APSP.