Minimum s-t cut interdiction problem

Abstract

This paper addresses a novel network interdiction problem, called the minimum s-t cut interdiction problem. It is a Stackelberg game containing two players: one evader and one interdictor. The evader wants to choose a minimum s-t cut in the network to cut any possible connection between two points s and t while the interdictor increases arc capacities under a budget constraint to make the minimum cut value as large as possible. In this paper, two classes of the problem are investigated: (1) the cost associated to any arc is proportional to the amount of its capacity increment; (2) the cost of any arc is fixed and independent from the amount of capacity changes. In the former, an algorithm is developed to solve the problem in polynomial time. In the latter, it is shown that the problem is strongly NP-hard and a Benders decomposition algorithm is proposed to solve the problem. Some experimental results on benchmarks and random data guarantee the correctness and performance of our proposed algorithms.