Modelling Network Resilience: The Complexity of Some Graph Division Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910229337210880 |
|---|---|
| author | Gutowski, Grzegorz Junosza-Szaniawski, Konstanty Lauerbach, Antonio Wolff, Alexander |
| author_facet | Gutowski, Grzegorz Junosza-Szaniawski, Konstanty Lauerbach, Antonio Wolff, Alexander |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17572 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Modelling Network Resilience: The Complexity of Some Graph Division Games Gutowski, Grzegorz Junosza-Szaniawski, Konstanty Lauerbach, Antonio Wolff, Alexander Computational Complexity Computer Science and Game Theory 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). |
| title | Modelling Network Resilience: The Complexity of Some Graph Division Games |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2605.17572 |