Distance-restricted firefighting on finite graphs

In the classic version of the game of firefighter, on the first turn a fire breaks out on a vertex in a graph G and then b firefighters protect b vertices. On each subsequent turn, the fire spreads to the collective unburned neighbourhood of all the burning vertices and the firefighters again protect b vertices. Once a vertex has been burned or protected it remains that way for the rest of the game. In distance-restricted firefighting the firefighters’ movement is restricted so they can only move up to some fixed distance d and they may or may not be permitted to move through burning vertices. In this paper we establish the NP-completeness of the distance-restricted versions of b -Firefighter and present an integer program for computing the exact value. We also discuss some interesting properties of the Expected Damage function.