The influence of maximum (s,t)-cuts on the competitiveness of deterministic strategies for the Canadian Traveller Problem

We study the $k$-Canadian Traveller Problem, where the objective is to lead a traveller in an undirected weighted graph $G$ from a source $s$ to a target $t$, knowing that at most $k$ edges of the graph are blocked and cannot be traversed. The locations of blockages are unknown at the beginning of the walk but a blocked edge is revealed when the traveller visits one of its endpoints. There exist graphs for which the competitive ratio of any deterministic strategies cannot be smaller than $2k+1$. Conversely, there exists a very simple strategy, textsc{reposition}, which achieves this ratio $2k+1$. It consists in successively traversing shortest $(s,t)$-paths and coming back to $s$ when the traveller is blocked. We refine this analysis by detecting families of graphs for which a smaller competitive ratio can be obtained. This paper produces a global analysis to understand the impact of the size of the maximum $(s,t)$-cuts of $G$ on the competitiveness of deterministic strategies. We show that when certain cut parameters are low compared to $k$, we are able to design deterministic strategies achieving a ratio $rho k + O(1)$, with $rho