Shortest Paths with Linear Edge Weights
Publisher Information
- Conf: FOCS 2026
Abstract
We study shortest paths in directed graphs whose edge weights are of the form \mathrm{wt}(e) = a_{e,1} \lambda_1 + a_{e,2} \lambda_2 + a_{e,3} \lambda_3 + \cdots + a_{e,d} \lambda_d + a_{e,d+1}. Here, each a_{e,i}\in\mathbb{R} is a fixed constant for each edge e, whereas each \lambda_i\in\mathbb{R} is common across the entire graph. So, there could be different shortest paths in the graph for different values of the \lambda_i’s. The number of such shortest paths is of interest in several combinatorial optimization problems. This is called the parametric shortest paths problem, and has been studied since the 1980s.
Carstensen (1983) showed that for d=1, the number of shortest paths in n-vertex graphs is at most n^{O(\log n)}, and also proved a matching lower bound of n^{\Omega(\log n)}. Mulmuley & Shah (2001) improved her construction, which was further enhanced by Gajjar & Radhakrishnan (2019) so that it also works for planar graphs. For d=2, they showed an upper bound of n^{O(\log^2 n)}. Barth, Funke & Proissl generalized their result to prove that n^{O(\log^d n)} is an upper bound for all positive integers d. The lower bound did not undergo any improvement over the years.
In this paper, we close this long line of research by showing that n^{O(d\log n)} is an upper bound for all positive integers d, drastically improving upon the earlier results. We observe that by trivially extending existing lower bound constructions for d=1, we can obtain a construction that achieves a matching lower bound of n^{\Omega(d\log n)} for all positive integers d. Our proof also works for undirected graphs with positive edge weights.
Furthermore, by building upon known work on the Point Location problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a Shortest Path Oracle which takes as input a point \overline{a}\in \mathbb{R}^d, and outputs a shortest path when \overline{\lambda}=\overline{a}, in sub-linear time (for a wide regime of d).
All earlier proofs of the upper bound proceeded by arranging the vertices of the graph in layers, splitting the graph across its middle layer into two halves, and then recursing on each half-graph. We deviate from this proof methodology by halving the graph in a different way: we eliminate all the odd-numbered layers and retain only the even-numbered layers, whilst maintaining certain shortest paths of the original graph in the half-graph. We observe how the properties of the edge weights and path weights of the initial graph in d-dimensional space change for the half-graph in the same space, which leads us to the required recurrence.