COVID on Trees and Infinite Grids

Abstract

We use Hartnell's model for virus spread on a graph, also known as firefighting. For rooted trees, we propose an Unburning Algorithm, a type of greedy algorithm starting from the leaves and working back towards the root. We show that the algorithm saves at least half the vertices of the optimal solution and that this is bound is sharp. We confirm a conjecture of Hartke about integrality gaps when comparing linear and integer program solutions. For general graphs, we propose a Containment Protocol, which looks ahead two time steps to decide where to place vaccinations. We show that the protocol performs near optimally on four well-studied infinite grids. The protocol is available for any graph and we realize this flexibility by investigating an infinite pentagonal graph.