All-Pairs Shortest Paths with Few Weights per Node

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 O(n (3+ω)/2 ) = O(n 2.686 ), improving on the 15-yearold subcubic bounds O(n (9+ω)/4 ) = O(n 2.843 ) [Chan; STOC '07] and 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.

• 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 positive results with simple hardness reductions even for undirected graphs. Interestingly, under fine-grained assumptions, the complexity in the undirected case jumps from Õ(n ω ) for d = 1 to n 2.5-o(1) for d ≥ 2.