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.
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:
- Locally-informed: The traveller learns the status of all edges incident to their current vertex, including those that appear in the future.
- 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.
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