Surviving rate of graphs and Firefighter Problem

doi:10.1007/s11464-022-1009-y

Front. Math. China

2022, Vol. 17

Issue (2) : 227-254 https://doi.org/10.1007/s11464-022-1009-y

SURVEY ARTICLE

Surviving rate of graphs and Firefighter Problem

Weifan WANG, Jiangxu KONG(

)

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

Download: PDF(299 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Jiangxu KONG

Issue Date: 23 May 2022

Cite this article:

Weifan WANG,Jiangxu KONG. Surviving rate of graphs and Firefighter Problem[J]. Front. Math. China, 2022, 17(2): 227-254.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-022-1009-y
https://academic.hep.com.cn/fmc/EN/Y2022/V17/I2/227

1	G Amir , R Baldasso , G Kozma . The firefighter problem on polynomial and intermediate growth groups. Discrete Math, 2020, 343 (11): 112077 https://doi.org/10.1016/j.disc.2020.112077
2	S Bessy , A Bonato , J Janssen , D Rautenbach , E Roshanbin . Burning a graph is hard. Discrete Appl Math, 2017, 232: 73- 87 https://doi.org/10.1016/j.dam.2017.07.016
3	S Bessy , A Bonato , J Janssen , D Rautenbach , E Roshanbin . Bounds on the burning number. Discrete Appl Math, 2018, 235: 16- 22 https://doi.org/10.1016/j.dam.2017.09.012
4	D P Biebighauser , L E Holte , R M Wagner . The firefighter problem for regular infinite directed grids. Involve, 2012, 5 (4): 393- 409 https://doi.org/10.2140/involve.2012.5.393
5	A Bonato , K Gunderson , A Shaw . Burning the plane: Densities of the infinite Cartesian grid. Graphs Combin, 36 (2022), 1311- 1335
6	A Bonato , J Janssen , E Roshanbin . How to burn a graph. Internet Math, 2016, 12 (1-2): 85- 100 https://doi.org/10.1080/15427951.2015.1103339
7	A Bonato , T Lidbetter . Bounds on the burning numbers of spiders and path-forests. Theoret Comput Sci, 2019, 794: 12- 19 https://doi.org/10.1016/j.tcs.2018.05.035
8	J A Bondy , U S R Murty . Graph Theory. Berlin: Springer, 2008
9	L Z Cai , Y Cheng , E Verbin , Y Zhou . Surviving rate of graphs with bounded treewidth for the firefighter problem. SIAM J Discrete Math, 2010, 24: 1322- 1335 https://doi.org/10.1137/100791130
10	L Z Cai , W F Wang . The surviving rate of a graph for the firefighter problem. SIAM J Discrete Math, 2009, 23: 1814- 1826
11	L Z Cai , E Verbin , L Yang . Firefighting on trees: (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm. Lecture Notes in Comput Sci, 2008, 5369: 258- 269
12	T Calamoneri , R Petreschi . L(h, 1)-labeling subclasses of planar graphs. J Parallel Distrib Comput, 2004, 64: 414- 426 https://doi.org/10.1016/j.jpdc.2003.11.005
13	J Chlebíková , M Chopin . The Firefighter Problem: A Structural Analysis, Parameterized and Exact Computation. Springer, 2014
14	J Chlebíková , M Chopin . The firefighter problem: further steps in understanding its complexity. Theoret Comput Sci, 2017, 676: 42- 51 https://doi.org/10.1016/j.tcs.2017.03.004
15	V Costa , S Dantas , M C Douradob , L Penso , D Rautenbach . More fires and more fighters. Discrete Appl Math, 2013, 161: 2410- 2419 https://doi.org/10.1016/j.dam.2013.04.008
16	V Costa , S Dantas , D Rautenbach . Asymptotic surviving rate of trees with multiple fire sources. Discrete Appl Math, 2015, 184: 14- 19 https://doi.org/10.1016/j.dam.2014.10.031
17	A Dean , S English , T Huang , R A Krueger , A Lee , M Mizrahi , C Wheaton-Werle . Firefighting on the hexagonal grid. Discrete Appl Math, 2021, 305: 16- 22 https://doi.org/10.1016/j.dam.2021.08.031
18	M Devlin , S Hartke . Fire containment in grids of dimension three and higher. Discrete Appl Math, 2007, 155: 2257- 2268 https://doi.org/10.1016/j.dam.2007.06.002
19	Z Dezso , A L Barabasi . Halting viruses in scale-free networks. Phys Rev E, 2002, 65: 055103 https://doi.org/10.1103/PhysRevE.65.055103
20	C Duffy . A collection of algorithmic and complexity results for variants of the firefighter problem. Master’s Thesis, University of Victoria, 2011
21	C Duffy . MacGillivray G. The firefighter problem: saving stes of vertices on cubic graphs. Networks, 2019, 74 (1): 62- 69
22	L Esperet , J Heuvel , F Maay , F Sipma . Fire containment in planar graphs. J Graph Theory, 2013, 73: 267- 279 https://doi.org/10.1002/jgt.21673
23	S Eubank , H Guclu , V S Kumar , M V Marathe , A Srinivasan , Z Toroczkai , N Wang . Modelling disease outbreaks in realistic urban social networks. Nature, 2004, 429 (6988): 180- 184 https://doi.org/10.1038/nature02541
24	O N Feldheim , R Hod . 3/2 firefighters are not enough. Discrete Appl Math, 2013, 161: 301- 306 https://doi.org/10.1016/j.dam.2012.08.005
25	S Finbow , B Hartnell , Q Li , K Schmeisser . On minimizing the effects of fire or a virus on a network. J Combin Math Combin Comput, 2000, 33: 311- 322
26	S Finbow , A King , G MacGillivray , R Rizzi . The firefighter problem for graphs of maximum degree three. Discrete Math, 2007, 307: 2094- 2105 https://doi.org/10.1016/j.disc.2005.12.053
27	S Finbow , G MacGillivray . The firefighter problem: a survey of results, directions and questions. Australas J Combin, 2009, 43: 57- 77
28	P Fogarty . Catching the fire on grids. Master’s Thesis, University of Vermont, USA, 2003
29	T Gavenčiak , J Kratochvíl , P Prałat . Firefighting on square, hexagonal, and triangular grids. Discrete Math, 2014, 337: 142- 155 https://doi.org/10.1016/j.disc.2014.06.020
30	P Gordinowicz . Planar graph is on fire. Theoret Comput Sci, 2015, 593: 160- 164 https://doi.org/10.1016/j.tcs.2015.06.002
31	P Gordinowicz . The 2-surviving rate of planar graphs with average degree lower than 9/2. J Graph Theory, 2018, 89: 341- 349 https://doi.org/10.1002/jgt.22254
32	S G Hartke . 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	B Hartnell . Firefighter! An application of domination Presentation at the 25th Manitoba Conference on Combinatorial Mathematics and Computing. University of Manitoba, Winnipeg, Canada, 1995
34	B Hartnell , Q Li . Firefighting on trees: How bad is the greedy algorithm? Congr Numer, 2000, 145: 187- 192
35	M Hiller , E Triesch , A Kosrer . On the burning number of p-caterpillars. manscript, 2019
36	X X Hu , W T Guo , Y M Qi , J X Kong . The edge surviving rate of Halin graphs. Util Math (to appear)
37	A King , G MacGillivray . The firefighter problem for cubic graphs. Discrete Math, 2010, 310: 614- 621 https://doi.org/10.1016/j.disc.2009.05.007
38	R Klein , C Levcopoulos , A Lingas . Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems. Algorithms, 2018, 11 (4): 45 https://doi.org/10.3390/a11040045
39	J X Kong , W F Wang , X D Zhu . The surviving rate of planar graphs. Theoret Comput Sci, 2012, 416: 65- 70 https://doi.org/10.1016/j.tcs.2011.10.002
40	J X Kong , L Z Zhang . A note on the surviving rate of 1-planar graphs. Discrete Math, 2017, 340: 1074- 1079 https://doi.org/10.1016/j.disc.2016.11.005
41	J X Kong , L Z Zhang . 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	J X Kong , L Z Zhang , W F Wang . The surviving rate of digraphs. Discrete Math, 2014, 334: 13- 19 https://doi.org/10.1016/j.disc.2014.06.018
43	J X Kong , L Z Zhang , W F Wang . Structural properties and surviving rate of planar graphs. Discrete Math Algorithms Appl, 2014, 6 (4): 1450052 https://doi.org/10.1142/S1793830914500529
44	M R Land , L Y Lu . An upper bound on the burning number of graphs Lecture Notes in Comput Sci, 10088. Springer, Cham, 2016, 54: 854- 857
45	Y Lin . Decomposition theorems for the treewidth of graphs. J Math Study, 2000, 33 (2): 113- 120
46	R Lipton , R Tarjan . A separator theorem for planar graphs. SIAM J Appl Math, 1979, 36: 177- 189 https://doi.org/10.1137/0136016
47	H Q Liu , X J Hu , X L Hu . Burning number of caterpillars. Discrete Appl Math, 2020, 284: 332- 340 https://doi.org/10.1016/j.dam.2020.03.062
48	H Q Liu , R T Zhang , X L Hu . Burning number of theta graphs. Appl Math Comput, 2019, 361: 246- 257
49	G MacGillivray , P Wang . On the firefighter problem. J Combin Math Combin Comput, 2003, 47: 83- 96
50	M E Messinger . Firefighting on Infinite Grids. Master’s Thesis, Dalhousie University, Canada, 2004
51	M E Messinger . Average firefighting on infinite grids. Australas J Combin, 2008, 41: 15- 28
52	D Mitsche , P Prałat , E Roshanbin . Burning graphs: a probabilistic perspective. Graphs Combin, 2017, 33: 449- 471 https://doi.org/10.1007/s00373-017-1768-5
53	D Mitsche , P Prałat , E Roshanbin Burning number of graph products. Theoret Comput Sci, 2018, 746: 124- 135 https://doi.org/10.1016/j.tcs.2018.06.036
54	D Moghbel . Topics in graph burning and datalog. Doctoral Thesis, Ryerson University, 2020
55	M E Newman , I Jensen , R M Ziff . Percolation and epidemics in a two-dimensional small world. Phys Rev E, 2002, 65 (2): 021904 https://doi.org/10.1103/PhysRevE.65.021904
56	R Pastor-Satorras , A Vespignani . Epidemic spreading in scale-free networks. Phys Rev Lett, 2001, 86 (14): 3200- 3203 https://doi.org/10.1103/PhysRevLett.86.3200
57	P Prałat . Sparse graphs are not flammable. SIAM J Discrete Math, 2013, 27: 2157- 2166 https://doi.org/10.1137/120876113
58	P Prałat . Graphs with average degree smaller than 30/11 burn slowly. Graphs Combin, 2014, 30: 455- 470 https://doi.org/10.1007/s00373-012-1265-9
59	N Ramos , C Souza , P Rezende . A matheuristic for the firefighter problem on graphs. Int Trans Oper Res, 2020, 27 (4): 739- 766
60	J M Read , M J Keeling . Disease evolution on networks: the role of contact structure. Proc Roy Soc London B, 2003, 270 (1516): 699- 708 https://doi.org/10.1098/rspb.2002.2305
61	A Scott , U Stege , N Zeh . Politician’s firefighting. Lecture Notes in Comput Sci, 2006, 4288: 608- 617
62	K A Sim , T S Tan , K B Wong . On the burning number of generalized petersen graphs. Bull Malays Math Sci Soc, 2018, 41: 1657- 1670 https://doi.org/10.1007/s40840-017-0585-6
63	E Stokstad . Biologists rush to protect Great Lakes from onslaught of carp. Science, 2010, 327 (5968): 932 https://doi.org/10.1126/science.327.5968.932
64	T S Tan , W C Teh . Graph burning: tight bounds on the burning numbers of path forests and spiders. Appl Math Comput, 2020, 385: 125447
65	W F Wang , S X Bao , J X Kong . The surviving rate of IC-graphs. J Liaoning Univ Natur Sci, 2018, 45: 331- 337 (in Chinese)
66	W F Wang , S Finbow , J X Kong . The 2-surviving rate of planar graphs without 6-cycles. Theoret Comput Sci, 2014, 518: 22- 31 https://doi.org/10.1016/j.tcs.2013.05.025
67	W F Wang , S Finbow , P Wang . The surviving rate of an infected network. Theoret Comput Sci, 2010, 411: 3651- 3660 https://doi.org/10.1016/j.tcs.2010.06.009
68	W F Wang , S Finbow , P Wang . A lower bound of the surviving rate of a planar graph with girth at least seven. J Comb Optim, 2014, 27: 621- 642 https://doi.org/10.1007/s10878-012-9541-4
69	W F Wang , J X Kong , L Z Zhang . The 2-surviving rate of planar graphs without 4- cycles. Theoret Comput Sci, 2012, 457: 158- 165 https://doi.org/10.1016/j.tcs.2012.07.011
70	W F Wang , K W Lih . 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 https://doi.org/10.1016/j.ejc.2005.09.002
71	W F Wang , X S Qiu , D J Huang . The surviving rate of some oriented planar graphs. J Zhejiang Norm Univ Natur Sci, 2016, 39: 241- 245 (in Chinese)
72	W F Wang , T T Wu , X X Hu , Y Q Wang . Planar graphs without chordal 5-cycles are 2-good. J Comb Optim, 2018, 35: 980- 996 https://doi.org/10.1007/s10878-017-0243-9
73	W F Wang , X B Yue , X D Zhu . The surviving rate of an outerplanar graph for the firefighter problem. Theoret Comput Sci, 2011, 412: 913- 921 https://doi.org/10.1016/j.tcs.2010.11.046
74	D J Watts , S Strogatz . Collective dynamics of small-world networks. Nature, 1998, 393 (6684): 440- 442 https://doi.org/10.1038/30918
75	T T Wu . The surviving rate of planar graphs. Master’s thesis, Zhejiang Normal Univeraity, 2015
76	T T Wu , J X Kong , W F Wang . The 2-surviving rate of planar graphs without 5-cycles. J Comb Optim, 2016, 31: 1479- 1492 https://doi.org/10.1007/s10878-015-9835-4
77	X B Yue , W F Wang . The surviving rate of Halin graphs. J Zhejiang Norm Univ Natur Sci, 2011, 34: 141- 144 (in Chinese)
78	M Zambon , P Rezende , C Souza . Finding exact solutions for the Geometric Firefighter Problem in practics. Comput Oper Res, 2018, 97: 72- 83 https://doi.org/10.1016/j.cor.2018.05.003
79	M Zambon , P Rezende , C Souza . Solving the geometric firefighter routing problem via integer programming. European J Oper Res, 2018, 274: 1090- 1101
80	D Zanette , M Kuperman . Effects of immunization in small-world epidemics. Physica A, 2002, 309 (3–4): 445- 452

[1]	Yuehua BU, Piaopiao YE. Injective coloring of planar graphs with girth 5[J]. Front. Math. China, 2022, 17(3): 473-484.
[2]	Xiaxia GUAN, Chuxiong WU, Weihua YANG, Jixiang MENG. A survey on book-embedding of planar graphs[J]. Front. Math. China, 2022, 17(2): 255-273.
[3]	Yue WANG, Jihong SHEN, Changjiang BU. Hypergraph characterizations of copositive tensors[J]. Front. Math. China, 2021, 16(3): 815-824.
[4]	Yongtao LIU. Perpetual cutoff method and $C D E ′$ (K,N) condition on graphs[J]. Front. Math. China, 2021, 16(3): 783-800.
[5]	Wen-Huan WANG, Ling YUAN. Uniform supertrees with extremal spectral radii[J]. Front. Math. China, 2020, 15(6): 1211-1229.
[6]	Yizheng FAN, Zhu ZHU, Yi WANG. Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices[J]. Front. Math. China, 2020, 15(3): 451-465.
[7]	Hongmei YAO, Li MA, Chunmeng LIU, Changjiang BU. Brualdi-type inclusion sets of Z-eigenvalues and l^k,s-singular values for tensors[J]. Front. Math. China, 2020, 15(3): 601-612.
[8]	Weizhong TIAN, Fengrong WEI, Thomas BROWN. Mixture network autoregressive model with application on students' successes[J]. Front. Math. China, 2020, 15(1): 141-154.
[9]	Xin LI, Jiming GUO, Zhiwen WANG. Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)[J]. Front. Math. China, 2019, 14(6): 1213-1230.
[10]	Xie-Bin CHEN. Matchings extend to Hamiltonian cycles in hypercubes with faulty edges[J]. Front. Math. China, 2019, 14(6): 1117-1132.
[11]	Lihua YOU, Xiaohua HUANG, Xiying YUAN. Sharp bounds for spectral radius of nonnegative weakly irreducible tensors[J]. Front. Math. China, 2019, 14(5): 989-1015.
[12]	Kinkar Chandra DAS, Huiqiu LIN, Jiming GUO. Distance signless Laplacian eigenvalues of graphs[J]. Front. Math. China, 2019, 14(4): 693-713.
[13]	Ziqiu LIU, Yunfeng ZHAO, Yuqin ZHANG. Perfect 3-colorings on 6-regular graphs of order 9[J]. Front. Math. China, 2019, 14(3): 605-618.
[14]	Thomas BRÜSTLE, Jie ZHANG. Non-leaving-face property for marked surfaces[J]. Front. Math. China, 2019, 14(3): 521-534.
[15]	Jun HE, Yanmin LIU, Junkang TIAN, Xianghu LIU. Upper bounds for signless Laplacian Z-spectral radius of uniform hypergraphs[J]. Front. Math. China, 2019, 14(1): 17-24.

Viewed

Full text

Abstract

Cited

Shared

Discussed