Probabilistic Firefighting

Abstract

Firefighting is a model used to study the spread of a fire on a graph G over discrete time-steps. Initially, a fire breaks out at some vertex of G. At each successive step , a firefighter defends an unburned vertex, and then the fire spreads to each unburned, undefended neighbour. The process terminates once the fire is stopped from spreading to any new vertices. We introduce probabilistic firefighting, where the fire only spreads to neighbours with a fixed probability. In this model, we say that the fire is contained if the probability that any new vertices burn is 0. We study strategies to contain a probabilistic fire on the kth power of a path and on the hexagonal grid. We conjecture that a probabilistic fire can be contained with one firefighter on the hexagonal grid, providing new insight into Messinger’s conjecture.