Canadian Traveler Problems in Temporal Graphs
摘要
We study the Canadian Traveler Problem (CTP), where a traveler aims to travel from a vertex s to a vertex t in a network containing up to k potentially blocked edges. These blocked edges remain unknown until the traveler visits one of their endpoints. We investigate this problem in temporal graphs where edges are only accessible at specific times. We study classical variants of the shortest path problem in temporal graphs. This paper formalizes the Canadian Traveler problem as a two-player positional game on graphs. In temporal graphs, the path can be viewed as a journey where the traveler takes trains from station s to station t. We consider two variants depending on how the traveler discovers a blocked edge (i.e., a canceled train). In the first variant, called locally-informed, the traveler learns which trains are canceled upon reaching a station. In the second variant, called uninformed, the traveler must wait until the departure time of the train to know whether it has been canceled or not. In the uninformed case, we provide a polynomial-time algorithm for each of the three shortest path variants. In the locally-informed case, we prove that finding a winning strategy for the traveler is PSPACE-complete. We also establish that the problem is polynomial-time solvable when \(k=1\) , but becomes NP-hard for \(k\ge 2\) . Additionally, we show that the standard (non-temporal) Canadian Traveler Problem is NP-hard when there are \(k\ge 4\) blocked edges. To the best of our knowledge, this represents the first hardness result for CTP with a constant number of blocked edges.