All-Pairs Shortest Paths with Few Weights per Node
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916810661560320 |
|---|---|
| author | Abboud, Amir Fischer, Nick Jin, Ce Williams, Virginia Vassilevska Xi, Zoe |
| author_facet | Abboud, Amir Fischer, Nick Jin, Ce Williams, Virginia Vassilevska Xi, Zoe |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | All-Pairs Shortest Paths with Few Weights per Node Abboud, Amir Fischer, Nick Jin, Ce Williams, Virginia Vassilevska Xi, Zoe Data Structures and Algorithms 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. |
| title | All-Pairs Shortest Paths with Few Weights per Node |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.20017 |