# All-Pairs Shortest Paths with Few Weights per Node

Preprint · Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi

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

## Abstract

We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most $d$ distinct weights on the outgoing edges from every node. For $d=n$ this is the classical (unrestricted) APSP problem that is hypothesized to require cubic time $n^{3-o(1)}$, and at the other extreme, for $d=1$, it is equivalent to the Node-Weighted APSP problem. We present new algorithms that achieve the following results: 1. Node-Weighted APSP can be solved in time $\\tilde{O}(n^{(3+ω)/2}) = \\tilde{O}(n^{2.686})$, improving on the 15-year-old subcubic bounds $\\tilde{O}(n^{(9+ω)/4}) = \\tilde{O}(n^{2.843})$ \[Chan; STOC '07\] and $\\tilde{O}(n^{2.830})$ \[Yuster; SODA '09\]. This positively resolves the question of whether Node-Weighted APSP is an \`\`intermediate'' problem in the sense of having complexity $n^{2.5+o(1)}$ if $ω=2$, in which case it also matches an $n^{2.5-o(1)}$ conditional lower bound. 2. For up to $d \\leq n^{3-ω-ε}$ distinct weights per node (where $ε\> 0$), the problem can be solved in subcubic time $O(n^{3-f(ε)})$ (where $f(ε) \> 0$). In particular, assuming that $ω= 2$, we can tolerate any sublinear number of distinct weights per node $d \\leq n^{1-ε}$, whereas previous work \[Yuster; SODA '09\] could only handle $d \\leq n^{1/2-ε}$ in subcubic time. This promotes our understanding of the APSP hypothesis showing that the hardest instances must exhaust a linear number of weights per node. Our result also applies to the All-Pairs Exact Triangle problem, thus generalizing a result of Chan and Lewenstein on "Clustered 3SUM" from arrays to matrices. Notably, our technique constitutes a rare application of additive combinatorics in graph algorithms.

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