Making Life Easier for Firefighters

Being a firefighter is a tough job, especially when tight city budgets do not allow enough firefighters to be on duty when a fire starts. This is formalized in the

Firefighter

problem, which aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. In every time step, a single additional firefighter may be placed on a vertex, and the fire advances to each vertex in its neighborhood that is not protected by a firefighter. 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

W

[1]-hard when parameterized by the number of saved vertices, and it is NP-hard to approximate within

n

1 − 

ε

for any

ε

 > 0. We aim to simplify the task of a firefighter by providing algorithms that show him/her how to efficiently fight fires in certain types of networks. We show that

Firefighter

can be solved in polynomial time on various well-known graph classes, including interval graphs, split graphs, permutation graphs, and

P

k

-free graphs for fixed

k

. On the negative side, we show that the problem remains NP-hard on unit disk graphs.