A bilevel critical node detection problem

Tools

Arulselvan, Ashwin and Chinchuluun, Altannar and Pardalos, Panos (2025) A bilevel critical node detection problem. Optimization Letters. ISSN 1862-4472 (https://doi.org/10.1007/s11590-025-02258-6)

[thumbnail of Arulselvan-etal-OL-2025-A-bilevel-critical-node-detection-problem]
Preview
 Text. Filename: Arulselvan-etal-OL-2025-A-bilevel-critical-node-detection-problem.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (2MB)| Preview

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.

ORCID iDs

Arulselvan, Ashwin ORCID logoORCID: https://orcid.org/0000-0001-9772-5523, Chinchuluun, Altannar and Pardalos, Panos;
CORE (COnnecting REpositories)