A polynomial-time combinatorial algorithm for shortest path interdiction problem

This paper addresses a special kind of network optimization interdiction problems, called the shortest path interdiction problem. The problem is a natural extension of the well-known shortest path problem in the presence of an adversary. The adversary is capable of increasing arc lengths under budget and bound constraints in a way that the shortest path length becomes large as much as possible. This paper considers the problem in the case that the cost of arc length increment is a linear function. It presents an algorithm to solve the problem in polynomial time.

Keywords:

Shortest path , Network interdiction , Stackelberg game