We investigate the complexity of shortest paths in time-dependent graphs where the costs of edges (that is, edge travel times) 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Θ(logn) times, settling a several-year-old conjecture of Dean (Technical Reports, 1999, 2004). However, 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. We also show that the complexity is polynomial if the slopes of the linear function come from a restricted class and describe an efficient scheme for computing a (1+ϵ)-approximation of the travel time function.
https://doi.org/10.1007/s00453-012-9714-7Cite as:
@article{Foschini_2012,
doi = {10.1007/s00453-012-9714-7},
url = {https://doi.org/10.1007%2Fs00453-012-9714-7},
year = 2012,
month = {nov},
publisher = {Springer Science and Business Media {LLC}},
volume = {68},
number = {4},
pages = {1075--1097},
author = {Luca Foschini and John Hershberger and Subhash Suri},
title = {On the Complexity of Time-Dependent Shortest Paths},
journal = {Algorithmica}
}