Multilevel Approaches for the Critical Node Problem

In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious viral attacks. On the one hand, network safety is investigated from a preventive perspective. On the other hand, blocking models have been proposed for scenarios in which the attack has already taken place causing a harmful spreading throughout the network. In this work, we combine these two perspectives. More precisely, following the framework defender–attacker–defender, we consider a model of prevention, attack, and damage containment using a three-stage, zero-sum game. The defender is not only able to adopt preventive strategies, but also to defend the network after an attack takes place. Assuming that the attacker acts optimally, we compute a defensive strategy for the first stage that minimizes the total damage to the network in the end of the third stage. Our contribution consists of considering this problem as a trilevel mixed-integer program and designing an exact algorithm for it based on tools developed for multilevel programming.