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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Canadian Traveler Problems in Temporal Graphs

  • Thomas Bellitto,
  • Johanne Cohen,
  • Bruno Escoffier,
  • Minh-Hang Nguyen,
  • Mikaël Rabie

摘要

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.