More fires and more fighters
Hartnell’s firefighter game models the containment of the spreading of an undesired property within a network. It is a one-player game played in rounds on a graph G in which a fire breaks out at f vertices of G . In each round the fire spreads to neighboring vertices unless the player defends these. The power of the player is limited in the sense that he can defend at most d additional vertices of G in each round. His objective is to save as many vertices as possible from burning. Most research on this game concerned the case f = d = 1 , which already leads to hard problems even restricted to trees. We study the game for larger values of f and d . We present useful properties of optimal strategies for the game on trees, efficient approximation algorithms, and bounds on the so-called surviving rate.