This paper examines the problem of interdicting the minimum \(st\) -cut, which can be viewed as a Stackelberg game with two types of players: evaders and interdictors. The goal of the evaders is to sever any connection between two crucial points by destroying certain links. They aim to find the minimum-cost cut to achieve this. Meanwhile, the interdictors, who are aware of the evaders’ objective, want to increase the cost of link destruction as much as possible. They can fortify the links to achieve this objective. This paper specifically focuses on the case where the cost of fortifying each link follows a convex piecewise-linear function. To tackle this problem, two polynomial-time algorithms are proposed. The first algorithm converts the problem into a root-finding problem involving a convex piecewise-linear function. It then employs a discrete-type Newton method to find the root in a finite number of iterations. The second algorithm is a modified version of the well-known successive shortest path algorithm. In order to assess the effectiveness of our proposed algorithms, we conduct computational experiments and compare them with a previous approach, which deals with linear costs. The results clearly demonstrate that our algorithms outperform the previous one in terms of speed and efficiency.
