Canadian Traveller Problems in Temporal Graphs

Thomas Bellitto, Johanne Cohen, Bruno Escoffier, Minh-Hang Nguyen, Mikaël RabiearXiv 2024 · DOI · arXiv

Introduction

The Canadian Traveller Problem (CTP) is a fundamental challenge in pathfinding under uncertainty. In its classic form, a traveller must navigate a graph where some edges may be blocked, but the status of an edge is only revealed upon reaching one of its endpoints. This paper extends the CTP to temporal graphs, where edges are only available at specific time steps. This extension models real-world scenarios such as flight schedules, public transportation, and time-varying communication networks.

An instance of the static Canadian Traveller Problem where a traveller must navigate from s to t with a budget, potentially facing blocked edges.

Information Models in Temporal Networks

The complexity of the Temporal CTP depends heavily on when the traveller receives information about blocked edges. The authors define two primary models:

  1. Locally-informed: The traveller learns the status of all edges incident to their current vertex, including those that appear in the future.
  2. Uninformed: The traveller only learns if an edge is blocked at the exact moment it is scheduled to exist.

Counter-intuitively, the locally-informed model is more computationally difficult (PSPACE-complete) than the uninformed model. In the locally-informed case, the traveller must evaluate a vast space of future contingencies, whereas the uninformed case can be simplified by the natural "lifespan" of temporal edges.

A temporal graph example illustrating how the timing of information (locally-informed vs. uninformed) changes the traveller's winning strategy.

Complexity Results

The research establishes a clear boundary between tractable and intractable variants of the problem:

  • Uninformed Case: Solvable in polynomial time using a dynamic programming approach on a "static expansion" of the temporal graph.
  • Locally-informed Case: Generally PSPACE-complete. While it is solvable in polynomial time for $k=1$ blocked edge, it becomes NP-hard for any $k \ge 2$.
  • Static CTP: The authors provide a significant breakthrough by proving that the static CTP is NP-hard for $k \ge 4$. This settles a long-standing question about the problem's complexity for small, constant numbers of edge failures.

Theoretical Insights

A key technique used in the proofs is the construction of "forced edges"—parallel edges that cannot be entirely blocked by the adversary. These are used to build logic gates that facilitate reductions from Quantified 3-SAT. Furthermore, the paper demonstrates that the temporal nature of the graph can actually simplify certain aspects of the problem by naturally pruning the search space of possible paths as time progresses.

Conclusion

By formalizing the Temporal CTP, this work provides a robust framework for understanding navigation in dynamic, uncertain environments. While uninformed variants are efficiently solvable, the strategic complexity of locally-informed models presents significant challenges. Future research may explore stochastic models where edge failures are probabilistic rather than adversarial, further bridging the gap between theory and real-world logistics.

Summary updated

Abstract

This paper formalises the Canadian Traveller problem as a positional two-player game on graphs. We consider two variants depending on whether an edge is blocked. In the locally-informed variant, the traveller learns if an edge is blocked upon reaching one of its endpoints, while in the uninformed variant, they discover this only when the edge is supposed to appear. We provide a polynomial algorithm for each shortest path variant in the uninformed case. This algorithm also solves the case of directed acyclic non-temporal graphs. In the locally-informed case, we prove that finding a winning strategy is PSPACE-complete. Moreover, we establish that the problem is polynomial-time solvable when $k=1$ but NP-hard for $k\geq 2$. Additionally, we show that the standard (non-temporal) Canadian Traveller Problem is NP-hard when there are $k\geq 4$ blocked edges, which is, to the best of our knowledge, the first hardness result for CTP for a constant number of blocked edges.
BibTeX
@misc{bellitto2024canadian,
  author = {Thomas Bellitto and Johanne Cohen and Bruno Escoffier and Minh-Hang Nguyen and Mikaël Rabie},
  title = {{Canadian Traveller Problems in Temporal Graphs}},
  year = {2024},
  eprint = {2407.16491},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.16491},
}
Figure