On a Class of Interdiction Problems with Partition Matroids: Complexity and Polynomial-Time Algorithms

In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision maker (referred to as a leader) and the lower-level decision maker (referred to as a follower) are induced by two distinct partition matroids with a common weighted ground set. Unlike classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent capacity constraints and engage in a zero-sum game. Although the problem of finding a maximum weight independent set in a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is NP-hard even when the weights of ground elements are all binary. On a positive note, it is revealed that, if the number of capacity constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial-time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a greedy algorithm for the leader.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.