The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence
Abstract
The Firefighter Problem models a spreading process (originally a fire, alternatively an infection or rumour, for example) on a graph. A defender saves a single vertex per turn; after each defence, the fire spreads to the unburned and undefended neighbours of all burning vertices. Deciding whether a strategy exists for the defender to protect some targeted number of vertices is computationally hard in graphs in general, but tractable in some restricted cases. Inspired by research into spreadable rabies vaccines for bats, we study a variant of the Firefighter problem in which defence also spreads. Some approximation results are already known for this problem; we provide algorithmic and hardness results, as well as containment results for the infinite n-dimensional Cartesian and strong grid graphs.
Related
- A free boundary problem for spreading of an invasive species in the territory of a native competitor under shifting climate
- Reaction-diffusion equations in periodic media: spreading speeds and spreading sets
- Spreading out perverse sheaves
- Spreading speeds for prey-predator systems in a shifting environment: a short proof
- Spreading speeds for nonlocal Fisher-KPP equations with time-dependent asymmetric kernels
BibTeX
@misc{enright2026infectious,
title = {{The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence}},
author = {Jessica Enright and Melissa A. Huggan and Ethan Hunter-Frankland and Margaret-Ellen Messinger and Dylan Pearson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05459},
eprint = {2610.05459},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05459},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Infectious Vaccination Problem: a variant of Firefighting with Spreading Defence
AU - Jessica Enright
AU - Melissa A. Huggan
AU - Ethan Hunter-Frankland
AU - Margaret-Ellen Messinger
AU - Dylan Pearson
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.05459
UR - https://arxiv.org/abs/2610.05459
AB - The Firefighter Problem models a spreading process (originally a fire, alternatively an infection or rumour, for example) on a graph. A defender saves a single vertex per turn; after each defence, the fire spreads to the unburned and undefended neighbours of all burning vertices. Deciding whether a strategy exists for the defender to protect some targeted number of vertices is computationally hard in graphs in general, but tractable in some restricted cases. Inspired by research into spreadable rabies vaccines for bats, we study a variant of the Firefighter problem in which defence also spreads. Some approximation results are already known for this problem; we provide algorithmic and hardness results, as well as containment results for the infinite n-dimensional Cartesian and strong grid graphs.
ER -