This entry is adapted from the peer-reviewed paper 2227-7390/11/1/179
The firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G. At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless they are defended by a firefighter that can move between any pair of vertices in a single time unit. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread.
1. Introduction
Bert Hartnell originally formulated the firefighter problem in 1995
[1]. It defines a discrete-time model of a diffusive process (e.g., a fire, a flood, an infectious disease, information, a computer virus, or an invasive species) on a graph
𝐺=(𝑉,𝐸), where a fire breaks out at a set of vertices
𝐹⊂𝑉. At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless a firefighter defends them. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread. A solution to the problem defines the defending actions that must be taken at each discrete time unit to optimally contain the spreading process by minimizing the number of burnt vertices or the time it takes to stop the diffusive process.
Over the years, the firefighter problem has gained growing relevance for its theoretical properties but also because it provides a simple model that can be used to study impactful phenomena such as the spreading and containment dynamics of viruses in social networks
[2] and fires in oil terminals
[3] and high-rise buildings
[4].
2. Properties and Algorithms
The firefighter problem has been extensively studied. It has been determined that it is
NP-hard for bipartite graphs
[5], for cubic graphs
[6], for trees of maximum degree three
[5] and of pathwidth three
[7], for co-bipartite graphs
[7], and unit disk graphs
[8]. It has also been established that the problem is in P for caterpillars and P-trees
[5], interval graphs, split graphs, permutation graphs,
𝑃𝑘-free graphs for fixed
k [8], and if the fire breaks out at a vertex of degree at most two, for graphs of maximum degree three
[9].
For the case of
𝑏≥2 firefighters, the problem is
NP-complete for trees of maximum degree
𝑏+2 and
NP-hard for the optimization version that maximizes the number of saved (unburnt) vertices for trees of maximum degree
𝑏+3 [10].
Regarding approximations, for the case of trees and a single firefighter, the greedy algorithm that every time selects the vertex that maximizes the number of protected vertices is a tight (
1/2)-approximation
[2][11]. There is also a (
1−1/𝑒)-approximation algorithm for rooted trees based on an LP-relaxation and randomized rounding
[12]. The previous algorithm was used by Iwaikawa et al. to provide a (0.7144)-approximation algorithm for ternary trees
[13]. The problem is not (
𝑛1−𝜖)-approximable on general graphs for any
𝜖∈(0,1) unless
𝑃=𝑁𝑃 [14]. More recently, Adjiashvili et al.
[15] presented a polynomial-time approximation scheme (PTAS) for trees.
From a parameterized point of view, the problem is W[1]-hard on general graphs for
𝑏≥1 firefighters when parameterized by the number of saved vertices, protected vertices, and burned vertices
[16].
3. Generalizations
The firefighter problem is a fundamental problem that helps understand diffusion and protection processes. However, from a practical point of view, it fails to capture essential aspects that arise in realistic scenarios. Therefore, many generalizations of the problem have been proposed over time; the following paragraphs list some of them.
Generalizations of the firefighter problem include a version where the number of available firefighters at each time is not constant
[17], a version where the objective is to protect a particular subset of the set of vertices
𝑆⊆𝑉 [6][10], a version where the protection also propagates from each defended vertex to their non-burning neighbors
[14][18], and a non-deterministic version where at each time the fire propagates to unprotected vertices with a given probability
[19]. There is also a fractional version where vertices can be partially burned and protected, and partially burned vertices can propagate their fractions of the fire to their undefended or partially defended neighbors
[20]. More recently, Coupechoux et al. introduced online versions of the firefighter and fractional firefighter problems where the number of available firefighters is revealed at each discrete time
[21]. The
k-firefighter problem is another generalization defined in terms of a two-player game where the fire propagates to at most
k vertices in each round with the objective of burning as many vertices as possible while the firefighter defends vertices to contain the spread of the fire
[22][23].
The geometric firefighter problem
[24][25][26] is another version that considers the speed with which barriers are constructed to contain the fire. In this variation, the fire starts at a point inside a simple polygon
𝒫 and circularly propagates at a constant speed. A firefighter sequentially builds a series of one-dimensional barriers at a constant speed, which can be different from the fire propagation speed, to contain the propagation of the fire. Barriers have to be built continuously before the fire reaches any of its points. The objective is to maximize the protected area of
𝒫, namely, the area separated from the fire by the barriers. Similarly to the original firefighter problem, the geometric firefighter problem assumes that the firefighter can be instantaneously transported from the last position of a recently constructed barrier to the origin of the next barrier in the solution. A similar but more general variant is the moving firefighter problem. In this problem, the time it takes a firefighter to move from a vertex
u to defend vertex
v is determined by a function
𝜏. This variant models situations such as a wildfire or a flood, where firefighters have to physically move from their current position to the location of an entity they intend to defend. It also incorporates the notion that entities modeled by the vertices are not necessarily instantaneously defended upon the arrival of a firefighter
[27].
In the traveling firefighter problem, also referred to as the
𝐿2-TSP (traveling salesperson problem), a firefighter has to extinguish a set of wildfires located at positions modeled by vertices. The distance between vertices is defined by a function
𝑑:𝑉×𝑉→ℝ≥0. A solution to this problem is a permutation of the vertices that minimize the total damage produced by the fires, which is a quadratic function of time elapsed from when the fires broke out to when the firefighter arrives
[28].
This entry is adapted from the peer-reviewed paper 2227-7390/11/1/179