# $\tilde{O}$ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost

Preprint · Manoj Gupta, Mrigankashekhar Shandilya

- Archive id: arxiv:2607.18714
- Published: 2026-07-21
- arXiv: https://arxiv.org/abs/2607.18714
- Citations: 0
- Source URL: https://arxiv.org/abs/2607.18714
- PDF: https://arxiv.org/pdf/2607.18714
- Provenance: arxiv

## Abstract

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 $Ω(n^2)$ since the output size is $Θ(n^2)$. A central goal in this area is to achieve a running time of $O(n^2)$. Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2001) designed an algorithm with a running time of $\\tilde{O}(n^2)$ 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 $\\tilde{O}(n^2)$ time and, with high probability, guarantees a 2-approximation for all pairs at distance at least $c$, where $c \\ge 0$ is a constant. Unlike the above two results, which were purely combinatorial, our algorithm combines combinatorial techniques with fast matrix multiplication (FMM).

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.