Complexity of the Multilevel Critical Node Problem
share
In this work, we analyze a sequential game played in a graph called the Multilevel Critical Node problem (MCN). A defender and an attacker are the players of this game. The defender starts by preventively interdicting vertices (vaccination) from being attacked. Then, the attacker infects a subset of non-vaccinated vertices and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected, and directed graphs, we clarify how the theoretical tractability of those problems vary. Our findings contribute with new NP-complete, Σ_2^p-complete and Σ_3^p-complete problems. Furthermore, for the last level of the game, the protection stage, we build polynomial time algorithms for certain graph classes.
READ FULL TEXT