Canadian Traveller Problems in Temporal Graphs.

-- Minh Hang Nguyen (IRIF)

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.

Category: seminars
Tags: Team seminar networks