Faster Approximate All Pairs Shortest Paths
Barna Saha, Christopher Ye · Society for Industrial and Applied Mathematics eBooks · 2024
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 Õ(n7/3). This result was recently improved by Deng, Kirkpatrick, Rong, Williams and Zhong to Õ(n2.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 Õ(n2.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.