Skip to main content
Springer Nature Link
Log in

Surviving rate of graphs and Firefighter Problem

  • Survey Article
  • Published:
Frontiers of Mathematics in China Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amir G, Baldasso R, Kozma G. The firefighter problem on polynomial and intermediate growth groups. Discrete Math, 2020, 343(11): 112077

    Article  MathSciNet  MATH  Google Scholar 

  2. Bessy S, Bonato A, Janssen J, Rautenbach D, Roshanbin E. Burning a graph is hard. Discrete Appl Math, 2017, 232: 73–87

    Article  MathSciNet  MATH  Google Scholar 

  3. Bessy S, Bonato A, Janssen J, Rautenbach D, Roshanbin E. Bounds on the burning number. Discrete Appl Math, 2018, 235: 16–22

    Article  MathSciNet  MATH  Google Scholar 

  4. Biebighauser D P, Holte L E, Wagner R M. The firefighter problem for regular infinite directed grids. Involve, 2012, 5(4): 393–409

    Article  MathSciNet  MATH  Google Scholar 

  5. Bonato A, Gunderson K, Shaw A. Burning the plane: Densities of the infinite Cartesian grid. Graphs Combin, 36 (2020), 1311–1335

    Article  MathSciNet  MATH  Google Scholar 

  6. Bonato A, Janssen J, Roshanbin E. How to burn a graph. Internet Math, 2016, 12(1–2): 85–100

    Article  MathSciNet  MATH  Google Scholar 

  7. Bonato A, Lidbetter T. Bounds on the burning numbers of spiders and path-forests. Theoret Comput Sci, 2019, 794: 12–19

    Article  MathSciNet  MATH  Google Scholar 

  8. Bondy J A, Murty U S R. Graph Theory. Berlin: Springer, 2008

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  10. Cai L Z, Wang W F. The surviving rate of a graph for the firefighter problem. SIAM J Discrete Math, 2009, 23: 1814–1826

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  12. Calamoneri T, Petreschi R. L(h, 1)-labeling subclasses of planar graphs. J Parallel Distrib Comput, 2004, 64: 414–426

    Article  MATH  Google Scholar 

  13. Chlebíková J, Chopin M. The Firefighter Problem: A Structural Analysis, Parameterized and Exact Computation. Springer, 2014

  14. Chlebíková J, Chopin M. The firefighter problem: further steps in understanding its complexity. Theoret Comput Sci, 2017, 676: 42–51

    Article  MathSciNet  MATH  Google Scholar 

  15. Costa V, Dantas S, Douradob M C, Penso L, Rautenbach D. More fires and more fighters. Discrete Appl Math, 2013, 161: 2410–2419

    Article  MathSciNet  MATH  Google Scholar 

  16. Costa V, Dantas S, Rautenbach D. Asymptotic surviving rate of trees with multiple fire sources. Discrete Appl Math, 2015, 184: 14–19

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Devlin M, Hartke S. Fire containment in grids of dimension three and higher. Discrete Appl Math, 2007, 155: 2257–2268

    Article  MathSciNet  MATH  Google Scholar 

  19. Dezso Z, Barabasi A L. Halting viruses in scale-free networks. Phys Rev E, 2002, 65: 055103

    Article  Google Scholar 

  20. Duffy C. A collection of algorithmic and complexity results for variants of the firefighter problem. Master’s Thesis, University of Victoria, 2011

  21. Duffy C. MacGillivray G. The firefighter problem: saving stes of vertices on cubic graphs. Networks, 2019, 74(1): 62–69

    Article  MathSciNet  MATH  Google Scholar 

  22. Esperet L, Heuvel J, Maay F, Sipma F. Fire containment in planar graphs. J Graph Theory, 2013, 73: 267–279

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  24. Feldheim O N, Hod R. 3/2 firefighters are not enough. Discrete Appl Math, 2013, 161: 301–306

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  26. Finbow S, King A, MacGillivray G, Rizzi R. The firefighter problem for graphs of maximum degree three. Discrete Math, 2007, 307: 2094–2105

    Article  MathSciNet  MATH  Google Scholar 

  27. Finbow S, MacGillivray G. The firefighter problem: a survey of results, directions and questions. Australas J Combin, 2009, 43: 57–77

    MathSciNet  MATH  Google Scholar 

  28. Fogarty P. Catching the fire on grids. Master’s Thesis, University of Vermont, USA, 2003

    Google Scholar 

  29. Gavenc̆iak T, Kratochvíl J, Prałat P. Firefighting on square, hexagonal, and triangular grids. Discrete Math, 2014, 337: 142–155

    Article  MathSciNet  MATH  Google Scholar 

  30. Gordinowicz P. Planar graph is on fire. Theoret Comput Sci, 2015, 593: 160–164

    Article  MathSciNet  MATH  Google Scholar 

  31. Gordinowicz P. The 2-surviving rate of planar graphs with average degree lower than 9/2. J Graph Theory, 2018, 89: 341–349

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  33. Hartnell B. Firefighter! An application of domination. Presentation at the 25th Manitoba Conference on Combinatorial Mathematics and Computing. University of Manitoba, Winnipeg, Canada, 1995

    Google Scholar 

  34. Hartnell B, Li Q. Firefighting on trees: How bad is the greedy algorithm? Congr Numer, 2000, 145: 187–192

    MathSciNet  MATH  Google Scholar 

  35. Hiller M, Triesch E, Kosrer A. On the burning number of p-caterpillars. manscript, 2019

  36. Hu X X, Guo W T, Qi Y M, Kong J X. The edge surviving rate of Halin graphs. Util Math (to appear)

  37. King A, MacGillivray G. The firefighter problem for cubic graphs. Discrete Math, 2010, 310: 614–621

    Article  MathSciNet  MATH  Google Scholar 

  38. Klein R, Levcopoulos C, Lingas A. Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. Algorithms, 2018, 11(4): 45

    Article  MathSciNet  MATH  Google Scholar 

  39. Kong J X, Wang W F, Zhu X D. The surviving rate of planar graphs. Theoret Comput Sci, 2012, 416: 65–70

    Article  MathSciNet  MATH  Google Scholar 

  40. Kong J X, Zhang L Z. A note on the surviving rate of 1-planar graphs. Discrete Math, 2017, 340: 1074–1079

    Article  MathSciNet  MATH  Google Scholar 

  41. 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)

    MathSciNet  MATH  Google Scholar 

  42. Kong J X, Zhang L Z, Wang W F. The surviving rate of digraphs. Discrete Math, 2014, 334: 13–19

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  44. Land M R, Lu L Y. An upper bound on the burning number of graphs. Lecture Notes in Comput Sci, 10088, Springer, Cham, 2016

    MATH  Google Scholar 

  45. Lin Y. Decomposition theorems for the treewidth of graphs. J Math Study, 2000, 33(2): 113–120

    MathSciNet  MATH  Google Scholar 

  46. Lipton R, Tarjan R. A separator theorem for planar graphs. SIAM J Appl Math, 1979, 36: 177–189

    Article  MathSciNet  MATH  Google Scholar 

  47. Liu H Q, Hu X J, Hu X L. Burning number of caterpillars. Discrete Appl Math, 2020, 284: 332–340

    Article  MathSciNet  MATH  Google Scholar 

  48. Liu H Q, Zhang R T, Hu X L, Burning number of theta graphs. Appl Math Comput, 2019, 361: 246–257

    Article  MathSciNet  MATH  Google Scholar 

  49. MacGillivray G, Wang P. On the firefighter problem. J Combin Math Combin Comput, 2003, 47: 83–96

    MathSciNet  MATH  Google Scholar 

  50. Messinger M E. Firefighting on Infinite Grids. Master’s Thesis, Dalhousie University, Canada, 2004

    MATH  Google Scholar 

  51. Messinger M E. Average firefighting on infinite grids. Australas J Combin, 2008, 41: 15–28

    MathSciNet  MATH  Google Scholar 

  52. Mitsche D, Prałat P, Roshanbin E. Burning graphs: a probabilistic perspective. Graphs Combin, 2017, 33: 449–471

    Article  MathSciNet  MATH  Google Scholar 

  53. Mitsche D. Prałat P, Roshanbin E. Burning number of graph products. Theoret Comput Sci, 2018, 746: 124–135

    Article  MathSciNet  MATH  Google Scholar 

  54. Moghbel D. Topics in graph burning and datalog. Doctoral Thesis, Ryerson University, 2020

  55. Newman M E, Jensen I, Ziff R M. Percolation and epidemics in a two-dimensional small world. Phys Rev E, 2002, 65(2): 021904

    Article  Google Scholar 

  56. Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys Rev Lett, 2001, 86(14): 3200–3203

    Article  Google Scholar 

  57. Prałat P. Sparse graphs are not flammable. SIAM J Discrete Math, 2013, 27: 2157–2166

    Article  MathSciNet  MATH  Google Scholar 

  58. Prałat P. Graphs with average degree smaller than \({{30} \over {11}}\) burn slowly. Graphs Combin, 2014, 30: 455–470

    Article  MathSciNet  MATH  Google Scholar 

  59. Ramos N, Souza C, Rezende P. A matheuristic for the firefighter problem on graphs. Int Trans Oper Res, 2020, 27(4): 739–766

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  61. Scott A, Stege U, Zeh N. Politician’s firefighting. Lecture Notes in Comput Sci, 2006, 4288: 608–617

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  63. Stokstad E. Biologists rush to protect Great Lakes from onslaught of carp. Science, 2010, 327(5968): 932

    Article  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  65. 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)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  67. Wang W F, Finbow S, Wang P. The surviving rate of an infected network. Theoret Comput Sci, 2010, 411: 3651–3660

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  71. 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)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  74. Watts D J, Strogatz S. Collective dynamics of small-world networks. Nature, 1998, 393(6684): 440–442

    Article  MATH  Google Scholar 

  75. Wu T T. The surviving rate of planar graphs. Master’s thesis, Zhejiang Normal Univeraity, 2015

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

    Article  MathSciNet  MATH  Google Scholar 

  77. Yue X B, Wang W F. The surviving rate of Halin graphs. J Zhejiang Norm Univ Natur Sci, 2011, 34: 141–144 (in Chinese)

    Google Scholar 

  78. Zambon M, Rezende P, Souza C. Finding exact solutions for the Geometric Firefighter Problem in practics. Comput Oper Res, 2018, 97: 72–83

    Article  MathSciNet  MATH  Google Scholar 

  79. Zambon M, Rezende P, Souza C. Solving the geometric firefighter routing problem via integer programming. European J Oper Res, 2018, 274: 1090–1101

    Article  MathSciNet  MATH  Google Scholar 

  80. Zanette D, Kuperman M. Effects of immunization in small-world epidemics. Physica A, 2002, 309(3–4): 445–452

    Article  MATH  Google Scholar 

Download references

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

  1. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China

    Weifan Wang & Jiangxu Kong

Authors
  1. Weifan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiangxu Kong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jiangxu Kong.

Additional information

Translated from Advances in Mathematics (China), 2021, 50(1): 1–21

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11464-022-1009-y

Keywords

MSC2020

Search

Navigation