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.

Key words： 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