Complexity of Firefighting on Graphs
Julius Althoetmar, Jamico Schade, Torben Schürenberg
我们考虑了一个追逐逃避游戏,它描述了在无方向图的节点上熄灭燃烧火灾的过程。 我们表示ffn(G)所需的最小消防员人数,并为ffn(G)=1和ffn(G)=2的图形以及完整的二叉树的几乎锐利的界限提供表征。 我们表明,决定给定 G 和 m 的 ffn(G) ≤ m 是否为 NP-hard。 此外,我们表明最短的策略可以具有超多项式长度,从而打开问题是否在NP中。 基于一些合理的猜想,我们也证明这个决策问题对于具有边界树荫的图形来说既不是NP-hard,也不是恒定m。
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 ffn(G) and provide a characterization for the graphs with ffn(G)=1 and ffn(G)=2 as well as almost sharp bounds for complete binary trees. We show that deciding whether ffn(G) ≤ m for given G and m is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the...