Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(s,t)-Cuts

The k-Canadian Traveller Problem consists in finding the optimal way from a source s to a target t on an undirected weighted graph G, knowing that at most k edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least 2k+1. Reposition and Comparison strategies achieve this bound. We refine this analysis by focusing on graphs with a maximum (s,t)-cut size mumax less than k. A strategy called Detour is proposed and its competitive ratio is 2mumax + sqrt{2}(k-mumax) + 1 when mumax k which is strictly less than 2k+1. Moreover, when mumax >= k, the competitive ratio of Detour is 2k+1 and is optimal. Therefore, Detour improves the competitiveness of the deterministic strategies known up to now.