Network Navigation with Online Delays is PSPACE-complete

Thomas Depian, Christoph Kern, Sebastian Röder, Soeren Terziadis, Markus Wallinger

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},
}
Figure