标题： 图上灭火问题的复杂性 显示英文标题

标题： Complexity of Firefighting on Graphs

摘要： 我们研究了一个描述扑灭在无向图节点上燃烧的火灾的追逐-逃脱博弈问题。我们将最少需要的消防员数量记作 $\text{ffn}(G)$，并刻画了具有 $\text{ffn}(G)=1$ 和 $\text{ffn}(G)=2$ 的图以及完全二叉树的几乎锐界。我们证明了对于给定的 $G$ 和 $m$，判断是否满足 $\text{ffn}(G) \leq m$ 是 NP-难的。此外，我们还表明最短策略可能具有超多项式长度，这使得问题是否属于 NP 仍悬而未决。 基于一些合理的猜想，我们还证明了这个决策问题既不是对于有界树宽图上的 NP-难问题，也不是对于常数 $m$ 上的 NP-难问题。 显示英文摘要

摘要： We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters required by $\text{ffn}(G)$ and provide a characterization for the graphs with $\text{ffn}(G)=1$ and $\text{ffn}(G)=2$ as well as almost sharp bounds for complete binary trees. We show that deciding whether $\text{ffn}(G) \leq m$ for given $G$ and $m$ is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the problem is in NP. Based on some plausible conjectures, we also prove that this decision problem is neither NP-hard for graphs with bounded treewidth nor for constant $m$.