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, two players P1 and P2 play a game with the following rules. P1 starts from s, and tries to arrive at t by tracing an edge on each move. P2 cuts 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 P2 can see the whole graph. P1 tries to minimize the sum of traveled edge 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 not the path length when the two players do their best is not greater than a certain positive integer is P-SPACE-complete, even if the weight on each edge is 1. (C) 1998 Scripta Technica.