Improved 2-Approximate Shortest Paths for close vertex pairs

Abstract

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 $\tilde{O}(n^{2+O\left(\frac{1}{k}\right )})$ time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least $k$ apart, where $k \ge 2$. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same $\tilde{O}(n^{2+\frac{1}{k}})$ runtime but applies to vertex pairs merely $O(\log k)$ apart, where $\log k \ge 1$. When $k=\log n$, the running time of our algorithm is $\tilde{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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.