THE SHORTEST-PATH PROBLEM WITH AN OBSTRUCTOR

Given, a graph G = (V, E), with two vertices s and t specified as the origin and destination, respectively; a positive integer K called the obstruction number; and (positive) weights l (.) on the edges; then, t wo players P1 and P2 play a game with the following rules. P1 starts f rom s, and tries to arrive at t by tracing an edge on each move. P2 cu ts in his turn, P2 cuts some edges. The maximum total number of edges that P2 can cut is K during the game. It is assumed that both P1 and P 2 can see the whole graph. P1 tries to minimize the sum of traveled ed ge weights (called the path length), and P2 tries to maximize the path length. This paper shows that the path length when the two players do their best can be determined in O(n(k-1) (m + n log n) (m = \E\, n = (\V\) time. It is also shown that the problem of deciding whether or n ot the path length when the two players do their best is not greater t han a certain positive integer is P-SPACE-complete, even if the weight on each edge is 1. (C) 1998 Scripta Technica.