论文标题
使消防员更加困惑的生活
Making Life More Confusing for Firefighters
论文作者
论文摘要
众所周知，战斗是一项艰巨的任务。消防员问题询问如何最佳地部署消防员以防御火灾的顶点。除了几类图表外，此问题都是NP完整的。值得庆幸的是，消防员不必独自工作，并且经常受到优秀的自然平民的努力，这些平民的努力通过在有能力的情况下维持防火方法来减缓火的传播。我们将证明，尽管有良好的意图，但不幸的是，这种帮助使消防员的最佳部署变得更加困难。为了建模这种情况，我们介绍了暂时的消防员问题，这是消防员的扩展到时间图。我们表明，颞消防员也是NP完整的，除了众所周知，消防员具有多项式时间解决方案的基础图中，所有的图表都如此。这促使我们在寻找障碍性时探索了图表的时间结构，并通过为时间图参数interval-membership-tidth提供了时间消防员的FPT算法来得出结论。
It is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem is NP-Complete on all but a few classes of graphs. Thankfully, firefighters do not have to work alone, and are often aided by the efforts of good natured civilians who slow the spread of a fire by maintaining firebreaks when they are able. We will show that this help, although well-intentioned, unfortunately makes the optimal deployment of firefighters an even harder problem. To model this scenario we introduce the Temporal Firefighter problem, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have polynomial time solutions. This motivates us to explore making use of the temporal structure of the graph in our search for tractability, and we conclude by presenting an FPT algorithm for Temporal Firefighter with respect to the temporal graph parameter vertex-interval-membership-width.
