ABSTRACT
The Firefighter graph process was first introduced by Hartnell, and it may be viewed as a simplified deterministic model of the spread of contagion in a network. In Firefighter, the process proceeds over discrete time-steps. There are k-many firefighters who are attempting to control the fire, where k is a positive integer. If a vertex is visited by a firefighter, then it can never burn in any subsequent round, and is called protected. The fire begins at some vertex in the first round, and the firefighter chooses some vertex to save. The fire spreads to all nonprotected neighbors at the beginning of each time-step; such vertices are called burned. A vertex is saved if it is not burned at the end of the process. Firefighter has been a considered in several familiar graph classes such as multi-dimensional grids and trees, and been studied both from a structural and algorithmic points of view. considering a variant of firefighting, called k-Constrained Firefighter.
