Title: The Stochastic Firefighter Problem,
Abstract: The dynamics of infectious diseases spread is crucial in determining their
risk and offering ways to contain them. We study sequential vaccination of
individuals in networks. In the original (deterministic) version of the
Firefighter problem, a fire breaks out at some node of a given graph. At each
time step, b nodes can be protected by a firefighter and then the fire spreads
to all unprotected neighbors of the nodes on fire. The process ends when the
fire can no longer spread. We extend the Firefighter problem to a probabilistic
setting, where the infection is stochastic. We devise a simple policy that only
vaccinates neighbors of infected nodes and is optimal on regular trees and on
general graphs for a sufficiently large budget. We derive methods for
calculating upper and lower bounds of the expected number of infected
individuals, as well as provide estimates on the budget needed for containment
in expectation. We calculate these explicitly on trees, d-dimensional grids,
and Erdős Rényi graphs. Finally, we construct a state-dependent budget
allocation strategy and demonstrate its superiority over constant budget
allocation on real networks following a first order acquaintance vaccination
policy.