Abstract
The Firefighter Problem on a graph can be viewed as a simplified model of the spread of contagion, fire, rumor, computer virus, etc. The fire breaks out at one or more vertices in a graph at the first round, and the firefighter chooses some vertices to protect. The fire spreads to all non-protected neighbors at the beginning of each time-step. The process stops when the fire can no longer spread. The Firefighter Problem has attracted considerable attention since it was introduced in 1995. In this paper we provide a survey on recent research progress of this field, including algorithms and complexity, Firefighter Problem for special graphs (finite and infinite) and digraphs, surviving rate and burning number of graphs. We also collect some open problems and possible research subjects.
Similar content being viewed by others
References
Amir G, Baldasso R, Kozma G. The firefighter problem on polynomial and intermediate growth groups. Discrete Math, 2020, 343(11): 112077
Bessy S, Bonato A, Janssen J, Rautenbach D, Roshanbin E. Burning a graph is hard. Discrete Appl Math, 2017, 232: 73–87
Bessy S, Bonato A, Janssen J, Rautenbach D, Roshanbin E. Bounds on the burning number. Discrete Appl Math, 2018, 235: 16–22
Biebighauser D P, Holte L E, Wagner R M. The firefighter problem for regular infinite directed grids. Involve, 2012, 5(4): 393–409
Bonato A, Gunderson K, Shaw A. Burning the plane: Densities of the infinite Cartesian grid. Graphs Combin, 36 (2020), 1311–1335
Bonato A, Janssen J, Roshanbin E. How to burn a graph. Internet Math, 2016, 12(1–2): 85–100
Bonato A, Lidbetter T. Bounds on the burning numbers of spiders and path-forests. Theoret Comput Sci, 2019, 794: 12–19
Bondy J A, Murty U S R. Graph Theory. Berlin: Springer, 2008
Cai L Z, Cheng Y, Verbin E, Zhou Y. Surviving rate of graphs with bounded treewidth for the firefighter problem. SIAM J Discrete Math, 2010, 24: 1322��1335
Cai L Z, Wang W F. The surviving rate of a graph for the firefighter problem. SIAM J Discrete Math, 2009, 23: 1814–1826
Cai L Z, Verbin E, Yang L. Firefighting on trees: (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm. Lecture Notes in Comput Sci, 2008, 5369: 258–269
Calamoneri T, Petreschi R. L(h, 1)-labeling subclasses of planar graphs. J Parallel Distrib Comput, 2004, 64: 414–426
Chlebíková J, Chopin M. The Firefighter Problem: A Structural Analysis, Parameterized and Exact Computation. Springer, 2014
Chlebíková J, Chopin M. The firefighter problem: further steps in understanding its complexity. Theoret Comput Sci, 2017, 676: 42–51
Costa V, Dantas S, Douradob M C, Penso L, Rautenbach D. More fires and more fighters. Discrete Appl Math, 2013, 161: 2410–2419
Costa V, Dantas S, Rautenbach D. Asymptotic surviving rate of trees with multiple fire sources. Discrete Appl Math, 2015, 184: 14–19
Dean A, English S, Huang T, Krueger R A, Lee A, Mizrahi M, Wheaton-Werle C. Firefighting on the hexagonal grid. Discrete Appl Math, 2021, 305: 16–22
Devlin M, Hartke S. Fire containment in grids of dimension three and higher. Discrete Appl Math, 2007, 155: 2257–2268
Dezso Z, Barabasi A L. Halting viruses in scale-free networks. Phys Rev E, 2002, 65: 055103
Duffy C. A collection of algorithmic and complexity results for variants of the firefighter problem. Master’s Thesis, University of Victoria, 2011
Duffy C. MacGillivray G. The firefighter problem: saving stes of vertices on cubic graphs. Networks, 2019, 74(1): 62–69
Esperet L, Heuvel J, Maay F, Sipma F. Fire containment in planar graphs. J Graph Theory, 2013, 73: 267–279
Eubank S, Guclu H, Kumar V S, Marathe M V, Srinivasan A, Toroczkai Z, Wang N. Modelling disease outbreaks in realistic urban social networks. Nature, 2004, 429(6988): 180–184
Feldheim O N, Hod R. 3/2 firefighters are not enough. Discrete Appl Math, 2013, 161: 301–306
Finbow S, Hartnell B, Li Q, Schmeisser K. On minimizing the effects of fire or a virus on a network. J Combin Math Combin Comput, 2000, 33: 311–322
Finbow S, King A, MacGillivray G, Rizzi R. The firefighter problem for graphs of maximum degree three. Discrete Math, 2007, 307: 2094–2105
Finbow S, MacGillivray G. The firefighter problem: a survey of results, directions and questions. Australas J Combin, 2009, 43: 57–77
Fogarty P. Catching the fire on grids. Master’s Thesis, University of Vermont, USA, 2003
Gavenc̆iak T, Kratochvíl J, Prałat P. Firefighting on square, hexagonal, and triangular grids. Discrete Math, 2014, 337: 142–155
Gordinowicz P. Planar graph is on fire. Theoret Comput Sci, 2015, 593: 160–164
Gordinowicz P. The 2-surviving rate of planar graphs with average degree lower than 9/2. J Graph Theory, 2018, 89: 341–349
Hartke S G. Attempting to narrow the integrality gap for the firefighter problem on trees. Discrete Methods in Epidemiology, J Abello, G Cormode. DIMACS Series in Discrete Math and Theoret Comput Sci, 2006, 70: 225–231
Hartnell B. Firefighter! An application of domination. Presentation at the 25th Manitoba Conference on Combinatorial Mathematics and Computing. University of Manitoba, Winnipeg, Canada, 1995
Hartnell B, Li Q. Firefighting on trees: How bad is the greedy algorithm? Congr Numer, 2000, 145: 187–192
Hiller M, Triesch E, Kosrer A. On the burning number of p-caterpillars. manscript, 2019
Hu X X, Guo W T, Qi Y M, Kong J X. The edge surviving rate of Halin graphs. Util Math (to appear)
King A, MacGillivray G. The firefighter problem for cubic graphs. Discrete Math, 2010, 310: 614–621
Klein R, Levcopoulos C, Lingas A. Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. Algorithms, 2018, 11(4): 45
Kong J X, Wang W F, Zhu X D. The surviving rate of planar graphs. Theoret Comput Sci, 2012, 416: 65–70
Kong J X, Zhang L Z. A note on the surviving rate of 1-planar graphs. Discrete Math, 2017, 340: 1074–1079
Kong J X, Zhang L Z. The edge surviving rate of a class of planar graphs for the firefighter problem. J Xiamen Univ Natur Sci, 2015, 54: 854–857 (in Chinese)
Kong J X, Zhang L Z, Wang W F. The surviving rate of digraphs. Discrete Math, 2014, 334: 13–19
Kong J X, Zhang L Z, Wang W F. Structural properties and surviving rate of planar graphs. Discrete Math Algorithms Appl, 2014, 6(4): 1450052
Land M R, Lu L Y. An upper bound on the burning number of graphs. Lecture Notes in Comput Sci, 10088, Springer, Cham, 2016
Lin Y. Decomposition theorems for the treewidth of graphs. J Math Study, 2000, 33(2): 113–120
Lipton R, Tarjan R. A separator theorem for planar graphs. SIAM J Appl Math, 1979, 36: 177–189
Liu H Q, Hu X J, Hu X L. Burning number of caterpillars. Discrete Appl Math, 2020, 284: 332–340
Liu H Q, Zhang R T, Hu X L, Burning number of theta graphs. Appl Math Comput, 2019, 361: 246–257
MacGillivray G, Wang P. On the firefighter problem. J Combin Math Combin Comput, 2003, 47: 83–96
Messinger M E. Firefighting on Infinite Grids. Master’s Thesis, Dalhousie University, Canada, 2004
Messinger M E. Average firefighting on infinite grids. Australas J Combin, 2008, 41: 15–28
Mitsche D, Prałat P, Roshanbin E. Burning graphs: a probabilistic perspective. Graphs Combin, 2017, 33: 449–471
Mitsche D. Prałat P, Roshanbin E. Burning number of graph products. Theoret Comput Sci, 2018, 746: 124–135
Moghbel D. Topics in graph burning and datalog. Doctoral Thesis, Ryerson University, 2020
Newman M E, Jensen I, Ziff R M. Percolation and epidemics in a two-dimensional small world. Phys Rev E, 2002, 65(2): 021904
Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys Rev Lett, 2001, 86(14): 3200–3203
Prałat P. Sparse graphs are not flammable. SIAM J Discrete Math, 2013, 27: 2157–2166
Prałat P. Graphs with average degree smaller than \({{30} \over {11}}\) burn slowly. Graphs Combin, 2014, 30: 455–470
Ramos N, Souza C, Rezende P. A matheuristic for the firefighter problem on graphs. Int Trans Oper Res, 2020, 27(4): 739–766
Read J M, Keeling M J. Disease evolution on networks: the role of contact structure. Proc Roy Soc London B, 2003, 270(1516): 699–708
Scott A, Stege U, Zeh N. Politician’s firefighting. Lecture Notes in Comput Sci, 2006, 4288: 608–617
Sim K A, Tan T S, Wong K B. On the burning number of generalized petersen graphs. Bull Malays Math Sci Soc, 2018, 41: 1657–1670
Stokstad E. Biologists rush to protect Great Lakes from onslaught of carp. Science, 2010, 327(5968): 932
Tan T S, Teh W C. Graph burning: tight bounds on the burning numbers of path forests and spiders. Appl Math Comput, 2020, 385: 125447
Wang W F, Bao S X, Kong J X. The surviving rate of IC-graphs. J Liaoning Univ Natur Sci, 2018, 45: 331–337 (in Chinese)
Wang W F, Finbow S, Kong J X. The 2-surviving rate of planar graphs without 6-cycles. Theoret Comput Sci, 2014, 518: 22–31
Wang W F, Finbow S, Wang P. The surviving rate of an infected network. Theoret Comput Sci, 2010, 411: 3651–3660
Wang W F, Finbow S, Wang P. A lower bound of the surviving rate of a planar graph with girth at least seven. J Comb Optim, 2014, 27: 621–642
Wang W F, Kong J X, Zhang L Z. The 2-surviving rate of planar graphs without 4-cycles. Theoret Comput Sci, 2012, 457: 158–165
Wang W F, Lih K W. On the sizes of graphs embeddable in surfaces of nonnegative Euler characteristic and their applications to edge choosability. European J Combin, 2007, 28: 111–120
Wang W F, Qiu X S, Huang D J. The surviving rate of some oriented planar graphs. J Zhejiang Norm Univ Natur Sci, 2016, 39: 241–245 (in Chinese)
Wang W F, Wu T T, Hu X X, Wang Y Q. Planar graphs without chordal 5-cycles are 2-good. J Comb Optim, 2018, 35: 980–996
Wang W F, Yue X B, Zhu X D. The surviving rate of an outerplanar graph for the firefighter problem. Theoret Comput Sci, 2011, 412: 913–921
Watts D J, Strogatz S. Collective dynamics of small-world networks. Nature, 1998, 393(6684): 440–442
Wu T T. The surviving rate of planar graphs. Master’s thesis, Zhejiang Normal Univeraity, 2015
Wu T T, Kong J X, Wang W F. The 2-surviving rate of planar graphs without 5-cycles. J Comb Optim, 2016, 31: 1479–1492
Yue X B, Wang W F. The surviving rate of Halin graphs. J Zhejiang Norm Univ Natur Sci, 2011, 34: 141–144 (in Chinese)
Zambon M, Rezende P, Souza C. Finding exact solutions for the Geometric Firefighter Problem in practics. Comput Oper Res, 2018, 97: 72–83
Zambon M, Rezende P, Souza C. Solving the geometric firefighter routing problem via integer programming. European J Oper Res, 2018, 274: 1090–1101
Zanette D, Kuperman M. Effects of immunization in small-world epidemics. Physica A, 2002, 309(3–4): 445–452
Acknowledgements
The first author was supported by the National Natural Science Foundation of China (No. 12031018). The second author was supported by China Postdoctoral Science Foundation (2020M681927) and the Fundamental Research Funds for the Provincial Universities of Zhejiang (2021YW08).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Advances in Mathematics (China), 2021, 50(1): 1–21
Rights and permissions
About this article
Cite this article
Wang, W., Kong, J. Surviving rate of graphs and Firefighter Problem. Front. Math. China 17, 227–254 (2022). https://doi.org/10.1007/s11464-022-1009-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11464-022-1009-y