STOC Conference 2025 Conference Paper
All-Pairs Shortest Paths with Few Weights per Node
- Amir Abboud
- Nick Fischer
- Ce Jin 0001
- Virginia Vassilevska Williams
- Zoe Xi
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: * Node-Weighted APSP can be solved in time Õ( n (3+ω)/2 ) = Õ( n 2.686 ), improving on the 15-year-old subcubic bounds Õ( n (9+ω)/4 ) = Õ( n 2.843 ) [Chan; STOC ’07] and Õ( 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. * For up to d ≤ 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 ≤ n 1−є , whereas previous work [Yuster; SODA ’09] could only handle d ≤ 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. With the current bounds on ω, we achieve a subcubic algorithm for d ≤ n 0.628 whereas previously a subcubic running time could only be achieved for d ≤ n 0.384 . 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. We complement our algorithmic results with simple hardness reductions extending the n 2.5− o (1) conditional lower bound for Node-Weighted APSP to undirected graphs. Interestingly, under fine-grained assumptions, the complexity in the undirected case jumps from O ( n ω ) for d =1 to n 2.5− o (1) for d ≥ 2.