FIGHTING INTELLIGENT FIRES IN GRAPHS

Abstract. 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 its neighbours over discrete time-steps. A firefighter saves 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. Consider a variant of the problem where the fire is intelligent but burns slowly. In the two-player game of k-Firefighter, for a fixed positive integer k, the fire chooses to burn at most k unsaved neighbours in a given round. The k-surviving rate of a graph G is defined as the expected percentage of vertices that can be saved in k-Firefighter when a fire breaks out at a random vertex of G. We supply bounds on the k-surviving rate, and determine its value for families of graphs including wheels and prisms. Contrary to the intuition that in a typical sparse graph most vertices can be saved, we show using spectral techniques that random d regular graphs have k-surviving rate at most (1+O(d −1/2)) k+1. We consider the limiting survival rate for countably infinite graphs. In particular, we show that the limiting survival rate of the infinite random graph can be any real number in [1/(k + 1), 1]. 1