Modelling Network Resilience: The Complexity of Some Graph Division Games
For network security researchers, this work establishes computational hardness limits for optimal controller placement under adversarial attacks, though results are largely theoretical and incremental.
The paper introduces a two-player zero-sum game modeling network resilience in software-defined networks, where a defender places controllers and an attacker deletes vertices. It proves that optimal strategies are NP-complete or Σ^P_2-complete for various game dynamics, but provides efficient algorithms for interval graphs and graphs of bounded treewidth.
Motivated by the controller placement problems in software-defined networks and the fair division principles of classical "cake cutting", we investigate the following two-player zero-sum game. In our model, a defender places a limited number of controllers on graph vertices, while an attacker deletes a limited number of vertices. The defender score is the total number of surviving vertices reachable from any remaining controller. We formalize the computational problems associated with various game dynamics (defender plays first; attacker plays first; players play simultaneously; pure or mixed strategies). We show that these natural problems are $\mathsf{NP}$-complete or $Σ^\mathsf{P}_2$-complete, depending on the specific variant. These hardness results provide limitations for optimal controller placement algorithms under different notions of quality of a solution. Finally, we present structural insights that yield efficient algorithms for restricted graph classes (namely interval graphs and graphs of bounded treewidth).