Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1 -- 1044 2023-07-21 00:52:40 |
2 Improved description + 9 word(s) 1053 2023-07-21 00:54:31 | |
3 Minor typo corrected Meta information modification 1053 2023-07-21 00:55:50 | |
4 format correct -9 word(s) 1044 2023-07-21 02:21:08 |

Video Upload Options

Do you have a full video?

Confirm

Are you sure to Delete?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
García Díaz, J. The Firefighter Problem. Encyclopedia. Available online: https://encyclopedia.pub/entry/47090 (accessed on 16 June 2024).
García Díaz J. The Firefighter Problem. Encyclopedia. Available at: https://encyclopedia.pub/entry/47090. Accessed June 16, 2024.
García Díaz, Jesús. "The Firefighter Problem" Encyclopedia, https://encyclopedia.pub/entry/47090 (accessed June 16, 2024).
García Díaz, J. (2023, July 21). The Firefighter Problem. In Encyclopedia. https://encyclopedia.pub/entry/47090
García Díaz, Jesús. "The Firefighter Problem." Encyclopedia. Web. 21 July, 2023.
The Firefighter Problem
Edit

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 (11/𝑒)-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
Information
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 524
Revisions: 4 times (View History)
Update Date: 21 Jul 2023
1000/1000
Video Production Service