Canadian Traveller Problems in Temporal Graphs.
Time: 14:00 -- Location: LRI, 445
summary: We focus on the Canadian Traveller Problem, where a traveller aims to travel on a network
from s to t with the minimum cost, considering that a maximum of k edges can be blocked. These
edges remain hidden from the traveller until they visit one of their endpoints. We have investigated
this problem in temporal graphs where edges are only accessible at specific times. Three classical
variants of the shortest path problem are considered: The Latest departure path, the Earliest arrival
path, and the Shortest duration path. This paper formalises this problem as a positional game in
two-player graphs. We consider two scenarios, depending on when we learn an edge is missing. If we need
to wait at an endpoint when we can go through the edge, we provide a polynomial algorithm for each of
the shortest path variants. This algorithm also solves the case of directed acyclic (non-temporal) graphs.
Moreover, if the traveller knows the set of missing edges in the future by being on a vertex, we prove
that finding a winning strategy is PSPACE-complete.
This is a joint work with Thomas Bellitto, Johanne Cohen, Bruno Escoffier, and Mikaël Rabie.