论文标题
多级关键节点问题的复杂性
Complexity of the Multilevel Critical Node Problem
论文作者
论文摘要
在这项工作中，我们分析了一个在称为多级关键节点问题（MCN）的图表中播放的连续游戏。防守者和攻击者是这场比赛的球员。防御者首先要预防性禁止对攻击的顶点（疫苗接种）。然后，攻击者感染了非接种疫苗的顶点的子集，最后，辩护人对保护策略做出了反应。我们提供了与MCN及其子游戏相关的第一个计算复杂性结果。此外，通过考虑统一，加权，无方向性和定向图，我们澄清了这些问题的理论障碍性如何变化。我们的发现带来了新的NP-Complete，$σ_2^p $ -complete和$σ_3^p $ -complete问题。此外，在游戏的最后级别，保护阶段，我们为某些图形类构建多项式时间算法。
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.
