Abstract
In the shortest path interdiction problem, an interdictor aims to remove arcs of total cost at most a given budget from a directed graph with given arc costs and traversal times such that the length of a shortest stpath is maximized. For static graphs, this problem is known to be strongly NPhard, and it has received considerable attention in the literature.
While the shortest path problem is one of the most fundamental and wellstudied problems also for temporal graphs, the shortest path interdiction problem has not yet been formally studied on temporal graphs, where common definitions of a "shortest path" include: latest start path (path with maximum start time), earliest arrival path (path with minimum arrival time), shortest duration path (path with minimum traveling time including waiting times at nodes), and shortest traversal path (path with minimum traveling time not including waiting times at nodes).
In this paper, we analyze the complexity of the shortest path interdiction problem on temporal graphs with respect to all four definitions of a shortest path mentioned above. Even though the shortest path interdiction problem on static graphs is known to be strongly NPhard, we show that the latest start and the earliest arrival path interdiction problems on temporal graphs are polynomialtime solvable. For the shortest duration and shortest traversal path interdiction problems, however, we show strong NPhardness, but we obtain polynomialtime algorithms for these problems on extensionparallel temporal graphs.
BibTeX  Entry
@InProceedings{boeckmann_et_al:LIPIcs.SAND.2023.9,
author = {Boeckmann, Jan and Thielen, Clemens and Wittmann, Alina},
title = {{Complexity of the Temporal Shortest Path Interdiction Problem}},
booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
pages = {9:19:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772754},
ISSN = {18688969},
year = {2023},
volume = {257},
editor = {Doty, David and Spirakis, Paul},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17945},
URN = {urn:nbn:de:0030drops179455},
doi = {10.4230/LIPIcs.SAND.2023.9},
annote = {Keywords: Temporal Graphs, Interdiction Problems, Complexity, Shortest Paths, Most Vital Arcs}
}
Keywords: 

Temporal Graphs, Interdiction Problems, Complexity, Shortest Paths, Most Vital Arcs 
Collection: 

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) 
Issue Date: 

2023 
Date of publication: 

12.06.2023 