All-Pairs Shortest Paths with Few Weights per Node

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 n3−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) = Õ(n2.686), improving on the 15-year-old subcubic bounds Õ(n(9+ω)/4) = Õ(n2.843) [Chan; STOC ’07] and Õ(n2.830) [Yuster; SODA ’09]. This positively resolves the question of whether Node-Weighted APSP is an ”intermediate” problem in the sense of having complexity n2.5+o(1) if ω=2, in which case it also matches an n2.5−o(1) conditional lower bound. * For up to d ≤ n3−ω−є distinct weights per node (where є > 0), the problem can be solved in subcubic time O(n3−f(є)) (where f(є) > 0). In particular, assuming that ω = 2, we can tolerate any sublinear number of distinct weights per node d ≤ n1−є, whereas previous work [Yuster; SODA ’09] could only handle d ≤ n1/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 ≤ n0.628 whereas previously a subcubic running time could only be achieved for d ≤ n0.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 n2.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 n2.5−o(1) for d ≥ 2.