Surviving rate of graphs and Firefighter Problem

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 fire-fighter 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, Fire-fighter 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.

Keywords

Graph / network / Firefighter Problem / surviving rate / burning number

References

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

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

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

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

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

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

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

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

[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

[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

[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

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

[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

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

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

[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

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

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

[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

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

[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

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

[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

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

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

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

[29] Gavenčiak T , Kratochvíl J , Prałat P . Firefighting on square, hexagonal, and triangular grids. Discrete Math, 2014, 337: 142- 155

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

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

[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

[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

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

[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

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

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

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

[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)

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

[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

[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, 54: 854- 857

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

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

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

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

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

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

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

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

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

[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

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

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

[58] Prałat P . Graphs with average degree smaller than 30/11 burn slowly. Graphs Combin, 2014, 30: 455- 470

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

[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

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

[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

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

[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

[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)

[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

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

[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

[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

[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

[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)

[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

[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

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

[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

[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)

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

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

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

RIGHTS & PERMISSIONS

Higher Education Press