2026/07/21 by Manoj Gupta, Mrigankashekhar Shandilya
#cs.DS
Given an undirected, unweighted graph G, we aim to compute a 2-approximation of all-pairs shortest paths (APSP). This problem admits a natural lower bound of Ω(n2) since the output size is Θ(n2). A central goal in this area is to achieve a running time of O(n2). Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of O(n2) that guarantees a 2-approximation only for pairs at a distance of at least O(log n). Recently, Gupta (FOCS 2025) improved this bound, handling all pairs at a distance of at least O(log log n). We nearly resolve this problem. We design a randomized algorithm that runs in O(n2) time and, with high probability, guarantees a 2-approximation for all pairs at distance at least c, where c ≥ 0 is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).