Javad Tayyebi - Department of Industrial Engineering, Birjand University of Technology, Birjand, Iran.
Hamid Bigdeli - Institute for the Study of War, Army Command and Staff University, Tehran, Iran.

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.

Shortest path, Network interdiction, Stackelberg game