Complexity Results on the Bi-Level Interdiction Knapsack Problem with Unit Interdiction Costs or Unit Weights

In this contribution we pursue the study of the Bi-level Interdiction Knapsack Problem, where a leader interdicts some knapsack items subject to a budget constraint in order to maximally reduce the total profit of the Knapsack Problem that the follower solves on the remaining items. We study the computational complexity of the problem when the leader’s interdiction costs are unitary and prove that the problem remains Σ2p-complete using a reduction from the bi-level 3-SAT problem. Additionally, we prove that the version with unitary lower level weights but arbitrary interdiction costs is NP-complete.