Fast 2-Approximate All-Pairs Shortest Paths

In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ (𝑛 2.5-𝑟 + 𝑛 𝜔 (𝑟 ) ) time, for any 𝑟 ∈ [0, 1]. This is 𝑂 (𝑛 2.032 ) time, using known bounds for rectangular matrix multiplication 𝑛 𝜔 (𝑟 ) [Le Gall, Urrutia, SODA 2018]. Our result improves on the Õ (𝑛 2.25 ) bound of [Roditty, STOC 2023], and on the Õ (𝑚 √ 𝑛 + 𝑛 2 ) bound of [Baswana, Kavitha, SICOMP 2010] for graphs with 𝑚 ≥ 𝑛 1.532 edges. For weighted graphs, we obtain (2 + 𝜖)-approximate APSP in Õ (𝑛 3-𝑟 + 𝑛 𝜔 (𝑟 ) ) time, for any 𝑟 ∈ [0, 1]. This is 𝑂 (𝑛 2.214 ) time using known bounds for 𝜔 (𝑟 ). It improves on the state of the art bound of 𝑂 (𝑛 2.25 ) by [Kavitha, Algorithmica 2012].

Our techniques further lead to improved bounds in a wide range of density for weighted graphs. In particular, for the sparse regime we construct a distance oracle in Õ (𝑚𝑛 2/3 ) time that supports 2-approximate queries in constant time. For sparse graphs, the preprocessing time of the algorithm matches conditional lower bounds [Patrascu, Roditty, Thorup, FOCS 2012; Abboud, Bringmann, Fischer, STOC 2023]. To the best of our knowledge, this is the first 2-approximate distance oracle that has subquadratic preprocessing time in sparse graphs.

We also obtain new bounds in the near additive regime for unweighted graphs. We give faster algorithms for (1 + 𝜖, 𝑘)approximate APSP, for 𝑘 = 2, 4, 6, 8.

We obtain these results by incorporating fast rectangular matrix multiplications into various combinatorial algorithms that carefully balance out distance computation on layers of sparse graphs preserving certain distance information.