Find in Library

In this paper, we develop solutions to the problem of identifying the <italic>k most vital cut-sets</italic> of a network under limited attacking resources in a network interdiction context. We treat three different versions of the problem, each having a different objective: namely, the highest probability of a successful attack, the least cost attack, and the least expected cost attack combining both success probability and attacking cost. We introduce a budget constraint to reflect the resource limitation of the attacker. We consider both the case of disjoint and non-disjoint cut-sets to target. We develop a simulation-optimization approach accounting for various techniques including the shortest path problem and the min-cut problem. The solution method is found to be very efficient even for large-scale networks. We implement the suggested algorithms for illustration purposes.