KIT | KIT-Bibliothek | Impressum | Datenschutz

NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times

Zeitz, Tim 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)


We study the complexity of earliest arrival problems on time-dependent networks with non-FIFO travel time functions, i.e. when departing later might lead to an earlier arrival. In this paper, we present a simple proof of the weak NP-hardness of the problem for travel time functions defined on integers. This simplifies and reproduces an earlier result from Orda and Rom. Our proof generalizes to travel time functions defined on rational numbers and also implies that, in this case, the problem becomes harder, i.e. is strongly NP-hard. As arbitrary functions are impractical for applications, we also study a more realistic problem model where travel time functions are piecewise linear and represented by a sequence of breakpoints with integer coordinates. We show that this problem formulation is strongly NP-hard, too. As an intermediate step for this proof, we also show the strong NP-completeness of SubsetProduct on rational numbers.

Verlagsausgabe §
DOI: 10.5445/IR/1000147976
Veröffentlicht am 22.06.2022
DOI: 10.1016/j.ipl.2022.106287
Zitationen: 4
Web of Science
Zitationen: 1
Zitationen: 3
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 01.2023
Sprache Englisch
Identifikator ISSN: 0020-0190, 1872-6119
KITopen-ID: 1000147976
Erschienen in Information Processing Letters
Verlag Elsevier
Band 179
Seiten Art.-Nr.: 106287
Schlagwörter Non-FIFO time-dependent shortest pathsNP-hardness; Theory of computation
Nachgewiesen in Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page