A bilevel critical node detection problem

Abstract In this study, we formulate a bilevel critical node detection problem for a given threat level and a budget. A leader has a budget to immunize a subset of nodes. An attacker, with the knowledge of the leader’s choice, will remove any set of non-immunized nodes within their budget, which is the threat level. The leader seeks to maximise the pairwise connectivity of the nodes for the worst case removal strategy of the attacker. We solve this problem using a high point relaxation within a branch-and-bound framework. We introduce some valid inequalities to strengthen the formulation and introduce a branching strategy to deal with the bilevel infeasibility. We test this procedure on two graph families with varying number of nodes, edge densities and budgets and share our computational experience.