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 O~(n2.5−r+nω(r)) time, for any r∈[0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, Urrutia, SODA 2018]. Our result improves on the O~(n2.25) bound of [Roditty, STOC 2023], and on the O~(mn−−√+n2) bound of [Baswana, Kavitha, SICOMP 2010] for graphs with m≥n1.532 edges. For weighted graphs, we obtain (2+ϵ)-approximate APSP in O~(n3−r+nω(r)) time, for any r∈[0,1]. This is O(n2.214) time using known bounds for ω(r). It improves on the state of the art bound of O(n2.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 O~(mn2/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+ϵ,k)-approximate APSP, for k=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.

• View at Publisher

Free Full Text ( Final Version , 1mb )