On the Complexity of Time-Dependent Shortest Paths
Luca Foschini, John E. Hershberger, Subhash Suri · 2011
We investigate the complexity of shortest paths in time-dependent graphs, in which the costs of edges vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. Our main result is that when the edge cost functions are (polynomial-size) piecewise linear, the shortest path from s to d can change nΘ(log n) times, settling a several-year-old conjecture of Dean [Technical Reports, 1999, 2004]. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class, present an output-sensitive algorithm for the general case, and describe a scheme for a (1 + ε)-approximation of the travel time function in near-quadratic space. Finally, despite the fact that the arrival time function may have superpolynomial complexity, we show that a minimum delay path for any departure time interval can be computed in polynomial time.