The Firefighter Problem: Comparison
View Latest Version
Please note this is a comparison between Version 4 by Catherine Yang and Version 3 by Jesús García Díaz.

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.

  • firefighter
  • graph theory
  • spread and containment in networks
  • networks

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].

References

  1. Hartnell, B. Firefighter! an application of domination. In Proceedings of the the 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Manitoba, Winnipeg, ON, Canada, 30 September–2 October 1994.
  2. Finbow, S.; MacGillivray, G. The Firefighter Problem: A survey of results, directions and questions. Australas. J. Comb. 2009, 43, 57–78.
  3. Khakzad, N. A graph theoretic approach to optimal firefighting in oil terminals. Energies 2018, 11, 3101.
  4. Wang, K.; Yuan, Y.; Chen, M.; Lou, Z.; Zhu, Z.; Li, R. A Study of Fire Drone Extinguishing System in High-Rise Buildings. Fire 2022, 5, 75.
  5. MacGillivray, G.; Wang, P. On the firefighter problem. JCMCC J. Comb. Math. Comb. Comput. 2003, 47, 57–78.
  6. King, A.; MacGillivray, G. The firefighter problem for cubic graphs. Discret. Math. 2010, 310, 614–621.
  7. Chlebíková, J.; Chopin, M. The firefighter problem: Further steps in understanding its complexity. Theor. Comput. Sci. 2017, 676, 42–51.
  8. Fomin, F.V.; Heggernes, P.; van Leeuwen, E.J. The firefighter problem on graph classes. Theor. Comput. Sci. 2016, 613, 38–50.
  9. Finbow, S.; King, A.; MacGillivray, G.; Rizzi, R. The firefighter problem for graphs of maximum degree three. Discret. Math. 2007, 307, 2094–2105.
  10. Bazgan, C.; Chopin, M.; Ries, B. The firefighter problem with more than one firefighter on trees. Discret. Appl. Math. 2013, 161, 899–908.
  11. Hartnell, B.; Li, Q. Firefighting on Trees: How Bad is the Greedy Algorithm? In Proceedings of the Thirty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium 145, Boca Raton, FL, USA, 11 September 2000; pp. 187–192.
  12. Cai, L.; Verbin, E.; Yang, L. Firefighting on trees: (1- 1/e)–approximation, fixed parameter tractability and a subexponential algorithm. In Proceedings of the International Symposium on Algorithms and Computation; Springer: Berlin, Germany, 2008; pp. 258–269.
  13. Iwaikawa, Y.; Kamiyama, N.; Matsui, T. Improved approximation algorithms for firefighter problem on trees. IEICE Trans. Inf. Syst. 2011, 94, 196–199.
  14. Anshelevich, E.; Chakrabarty, D.; Hate, A.; Swamy, C. Approximation algorithms for the firefighter problem: Cuts over time and submodularity. In Proceedings of the International Symposium on Algorithms and Computation; Springer: Berlin, Germany, 2009; pp. 974–983.
  15. Adjiashvili, D.; Baggio, A.; Zenklusen, R. Firefighting on trees beyond integrality gaps. ACM Trans. Algorithms (TALG) 2018, 15, 1–33.
  16. Bazgan, C.; Chopin, M.; Cygan, M.; Fellows, M.R.; Fomin, F.V.; Van Leeuwen, E.J. Parameterized complexity of firefighting. J. Comput. Syst. Sci. 2014, 80, 1285–1297.
  17. Ng, K.L.; Raff, P. A generalization of the firefighter problem on Z × Z. Discret. Appl. Math. 2008, 156, 730–745.
  18. Anshelevich, E.; Chakrabarty, D.; Hate, A.; Swamy, C. Approximability of the firefighter problem. Algorithmica 2012, 62, 520–536.
  19. Michalak, K.; Knowles, J.D. Simheuristics for the multiobjective nondeterministic firefighter problem in a time-constrained setting. In Proceedings of the European Conference on the Applications of Evolutionary Computation; Springer: Berlin, Germany, 2016; pp. 248–265.
  20. Fogarty, P. Catching the Fire on Grids. Master’s Thesis, Department of Mathematics, University of Vermont, Burlington, VT, USA, 2003.
  21. Coupechoux, P.; Demange, M.; Ellison, D.; Jouve, B. Firefighting on trees. Theor. Comput. Sci. 2019, 794, 69–84.
  22. Develin, M.; Hartke, S.G. Fire containment in grids of dimension three and higher. Discret. Appl. Math. 2007, 155, 2257–2268.
  23. Bonato, A.; Messinger, M.E.; Prałat, P. Fighting constrained fires in graphs. Theor. Comput. Sci. 2012, 434, 11–22.
  24. Klein, R.; Levcopoulos, C.; Lingas, A. Approximation algorithms for the geometric firefighter and budget fence problems. In Proceedings of the Latin American Symposium on Theoretical Informatics; Springer: Berlin, Germany, 2014; pp. 261–272.
  25. Klein, R.; Levcopoulos, C.; Lingas, A. Approximation algorithms for the geometric firefighter and budget fence problems. Algorithms 2018, 11, 45.
  26. Zambon, M.J.; de Rezende, P.J.; de Souza, C.C. Solving the geometric firefighter routing problem via integer programming. Eur. J. Oper. Res. 2019, 274, 1090–1101.
  27. Gutiérrez-De-La-Paz, B.R.; García-Díaz, J.; Menchaca-Méndez, R.; Montenegro-Meza, M.A.; Menchaca-Méndez, R.; Gutiérrez-De-La-Paz, O.A. The Moving Firefighter Problem. Mathematics 2023, 11, 179.
  28. Farhadi, M.; Toriello, A.; Tetali, P. The Traveling Firefighter Problem. In Proceedings of the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), Philadelphia, PA, USA, 19–21 July 2021; pp. 205–216.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback