# Improved Additive Approximation Algorithms for APSP

Preprint · Ce Jin, Yael Kirkpatrick, Michał Stawarz, Virginia Vassilevska Williams

- Archive id: arxiv:2511.04775
- Published: 2025-11-06
- arXiv: https://arxiv.org/abs/2511.04775
- Source URL: https://arxiv.org/abs/2511.04775
- PDF: https://arxiv.org/pdf/2511.04775
- Provenance: arxiv

## Abstract

The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, beginning with the work of Dor, Halperin and Zwick \[SICOMP'01\]. Many recent works have attempted to improve these original algorithms using the algebraic tools of fast matrix multiplication. We improve on these results for the following problems. For $+2$-approximate APSP, the state-of-the-art algorithm runs in $O(n^{2.259})$ time \[Dürr, IPL 2023; Deng, Kirkpatrick, Rong, Vassilevska Williams, and Zhong, ICALP 2022\]. We give an improved algorithm in $O(n^{2.2255})$ time. For $+4$ and $+6$-approximate APSP, we achieve time complexities $O(n^{2.1462})$ and $O(n^{2.1026})$ respectively, improving the previous $O(n^{2.155})$ and $O(n^{2.103})$ achieved by \[Saha and Ye, SODA 2024\]. In contrast to previous works, we do not use the big hammer of bounded-difference $(\\min,+)$-product algorithms. Instead, our algorithms are based on a simple technique that decomposes the input graph into a small number of clusters of constant diameter and a remainder of low degree vertices, which could be of independent interest in the study of shortest paths problems. We then use only standard fast matrix multiplication to obtain our improvements.

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

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