The Firefighter problem on graph classes

The Firefighter problem aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. At every time step a new firefighter may be placed on some vertex, and then the fire advances to every vertex that is not protected by a firefighter and has a neighbor on fire. The problem is notoriously hard: it is NP-hard even when the input graph is a bipartite graph or a tree of maximum degree 3, it is NP-hard to approximate within n 1 − ϵ for any ϵ > 0, and it is W [ 1 ] -hard when parameterized by the number of saved vertices. We show that Firefighter can be solved in polynomial time on interval graphs, split graphs, permutation graphs, and P k -free graphs for fixed k. To complement these results, we show that the problem remains NP-hard on unit disk graphs.

Authors

• Fedor V. Fomin
• Pinar Heggernes
• Erik Jan van Leeuwen

Keywords

• Firefighter problem
• Algorithms
• Interval graphs
• Permutation graphs
• Split graphs
• P k -free graphs