The Canadian Traveller Problem

Abstract

Suppose that a road map is given in which each road is associated with the time it takes to traverse it. However, this road map is unreliable; some of the roads might be unsuitable for travel at certain times, and such blockage would be revealed only upon reaching an adjacent site. The Canadian Traveller Problem is to devise a travel strategy that would guarantee a good path between two sites given this uncertainty. Papadimitriou and Yannakakis proved that if the number of roads that might be blocked is not fixed, then devising a strategy that guarantees a given competitive ratio is PSPACE-complete. In this paper, we study several variations of this problem. • In the Recoverable Canadian Traveller Problem, each site is associated with a recovery time to reopen any blocked road that is adjacent to it. We present a polynomial-time travel strategy that guarantees the shortest worst-case travel time, in the case where an upper bound on the number of blockages is known in advance, and the recovery times are not long relative to the travel times. • In the stochastic variation of the Recoverable Cansidian Traveller Problem, each road is associated with an independent probability of being blocked. For this problem, we present a polynomial-time strategy that minimizes the expected travel time, in the case where the recovery times are not long relative to the travel times. • Another variation considered is the fc-Canadian Traveller Problem. Here, an upper bound, k, on the number of blocked roads is given as a parameter. We present a travel strategy that guarantees the shortest worst-case travel time. The time complexity of devising this strategy is polynomial for any constant k. On the other hand, we prove that devising such a strategy when k is non-constant is PSPACE-complete. • A "dual" problem to the Canadian Traveller Problem is the k-Vital Edges Problem. Given a road map and two specified sites, find k roads whose blockage would maximize the increase in the travel time between the two sites. We prove that this problem is NP-hard, even when the travel time of all the roads is constant. The Canadian Traveller Problem and its variations can be viewed as routing problems. In many communication networks messages routing is done according to an outdated topology of the network. Our algorithms could replace existing routing schemes to achieve more robust routing.