# Fast 2-Approximate All-Pairs Shortest Paths

Article · Michal Dory, Sebastian Forster, Yael Kirkpatrick, Yasamin Nazari, Virginia Vassilevska Williams, Tijn de Vos

- Archive id: arxiv:2307.09258
- Published: 2023-07-18
- Venue: Society for Industrial and Applied Mathematics eBooks
- DOI: https://doi.org/10.1137/1.9781611977912.169
- arXiv: https://arxiv.org/abs/2307.09258
- Citations: 0
- Source URL: https://arxiv.org/abs/2307.09258
- PDF: https://arxiv.org/pdf/2307.09258
- Provenance: arxiv

## Abstract

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 $\\tilde O(n^{2.5-r}+n^{ω(r)})$ time, for any $r\\in\[0,1\]$. This is $O(n^{2.032})$ time, using known bounds for rectangular matrix multiplication $n^{ω(r)}$ \[Le Gall, Urrutia, SODA 2018\]. Our result improves on the $\\tilde{O}(n^{2.25})$ bound of \[Roditty, STOC 2023\], and on the $\\tilde{O}(m\\sqrt n+n^2)$ bound of \[Baswana, Kavitha, SICOMP 2010\] for graphs with $m\\geq n^{1.532}$ edges. For weighted graphs, we obtain $(2+ε)$-approximate APSP in $\\tilde O(n^{3-r}+n^{ω(r)})$ time, for any $r\\in \[0,1\]$. This is $O(n^{2.214})$ time using known bounds for $ω(r)$. It improves on the state of the art bound of $O(n^{2.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 $\\tilde O(mn^{2/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.

_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.