Fighting constrained fires in graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Anthony Bonato^a ; ^{abonato@ryerson.ca} ; Margaret-Ellen Messinger^b ; ^{mmessinger@mta.ca} ; Pawe艂 Pra艂at^a ; ^{pralat@ryerson.ca}
• 关键词：Firefighter ; Surviving rate ; Random regular graphs ; Infinite random graph
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：25 May, 2012
• 卷：434
• 期：Complete
• 页码：11-22
• 文件大小：338 K

摘要

The firefighter problem is a simplified model for the spread of a fire (or disease or computer virus) in a network. A fire breaks out at a vertex in a connected graph, and spreads to each of its unprotected neighbours over discrete time-steps. A firefighter protects one vertex in each round which is not yet burned. While maximizing the number of saved vertices usually requires a strategy on the part of the firefighter, the fire itself spreads without any strategy. We consider a variant of the problem where the fire is constrained by spreading to a fixed number of vertices in each round. In the two-player game of -firefighter, for a fixed positive integer , the fire chooses to burn at most unprotected neighbours in a given round. The -surviving rate of a graph is defined as the expected percentage of vertices that can be saved in -firefighter when a fire breaks out at a random vertex of .

We supply bounds on the -surviving rate, and determine its value for families of graphs including wheels and prisms. We show using spectral techniques that random regular graphs have -surviving rate at most . We consider the limiting surviving rate for countably infinite graphs. In particular, we show that the limiting surviving rate of the infinite random graph can be any real number in .