Let G=(V,A) be a directed graph with (positive) length l(a) for each a∈A, and two vertices s and t are specified. Player 1 and Player 2 play reciprocally on G according to the following rules until Player 1 reaches t. Player 1 attempts to move from starting point s to destination t, moving along one arc during each turn. Player 2 can delete within a game is K. Both Player 1 and Player 2 completely know the graph and see the action of the enemy at all times. Player 1 tries to keep the sum of the length of arcs which he passed through to a minimum value (the sum is defined to be infinite if Player 1 cannot reach t), µwhile Player 2 attempts to make it as large as possible. What value will it be? Notice that Player 2 can delete an edge after Player 1 has passed through it. In this paper, the authors show that the problem can be solved in O(nK(m+nlogn)) time (m=∈A∈, n=∈V∈), and that it is P-SPACE-complete even if l(a)=1 for all a∈A [In Japanese.]
