Abstract
We study shortest paths in directed graphs whose edge weights are of the form $$ mathsf{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}inmathbb{R}$ is a fixed constant for each edge $e$, whereas each $lambda_i$ is a shared variable 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 emph{Parametric Shortest Paths} problem, and has been studied since the 1980s.
For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(log n)}$. She also proved a matching lower bound of $n^{Omega(log n)}$, which was later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(log^d n)}$ 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 an $n^{O(dlog n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Omega(dlog n)}$ can be obtained by trivially extending existing lower bound constructions for $d=1$. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. Furthermore, for directed graphs whose edge weights are univariate polynomials of degree at most $q$, we prove an upper bound of $n^{O(log{n}+log{q})}$.
Finally, building upon work on the emph{Point Location} problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a emph{Shortest Path Oracle} which takes as input a point $overline{x}in mathbb{R}^d$, and outputs a shortest path at $overline{lambda}=overline{x}$ in sublinear time (for a wide regime of $d$).
All earlier upper bound proofs 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 requisite shortest paths of the original graph. We then view shortest paths in the half-graph as convex objects in $d$-dimensional space, which leads us to the required recurrence.
