Network Navigation with Online Delays is PSPACE-complete
Lists
Only you see this
Abstract
In public transport networks disruptions may occur and lead to travel delays. It is thus interesting to determine whether a traveler can be resilient to delays that occur unexpectedly, ensuring that they can reach their destination in time regardless. We model this as a game between the traveler and a delay-introducing adversary. We study the computational complexity of the problem of deciding whether the traveler has a winning strategy in this game. Our main result is that this problem is PSPACE-complete.
BibTeX
@misc{depian2023network,
author = {Thomas Depian and Christoph Kern and Sebastian Röder and Soeren Terziadis and Markus Wallinger},
title = {{Network Navigation with Online Delays is PSPACE-complete}},
year = {2023},
eprint = {2308.12265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2308.12265},
}