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 n1−ϵn1−ϵ for any ϵ>0ϵ>0, and it is W[1]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 PkPk-free graphs for fixed k. To complement these results, we show that the problem remains NP-hard on unit disk graphs.