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 GG in which a fire breaks out at ff vertices of GG. 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 dd additional vertices of GG 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=1f=d=1, which already leads to hard problems even restricted to trees.We study the game for larger values of ff and dd. We present useful properties of optimal strategies for the game on trees, efficient approximation algorithms, and bounds on the so-called surviving rate.