Improved 2-Approximate Shortest Paths for close vertex pairs

An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in O(n 2+O( 1 k ) ) time 1 , ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least k apart, where k ⩾ 2. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same O(n 2+ 1 k ) runtime but applies to vertex pairs merely O(log k) apart, where log k ⩾ 1. When k = log n, the running time of our algorithm is O(n 2 ) and it works for all pairs at least O(log log n) apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.

Observation 1.1. A +k-approximate APSP algorithm provides 2-approximate distances for all vertex pairs with a distance of at least k.

Using this observation, the above algorithms produce 2-approximate answers for vertex pairs sufficiently far apart. Thus, +2-approximate algorithm of [ACIM99] implies a 2-approximate APSP algorithm with a running 1 O() notation hides polylog n factors 1