Resource minimization for fire containment

We consider the following model for fire containment. We are given an undirected graph G = (V, E) with a source vertex s where the fire starts. At each time step, the firefighters can save up to k vertices of the graph, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. Our goal is to choose the vertices to be saved at each time step so as to contain the fire. This is a simple mathematical model abstracting the dynamic nature of fire containment and other natural processes, such as, for example, the spread of a perfectly contagious disease and its containment via vaccination. We focus on the Resource Minimization Fire Containment (RMFC) problem, where we are additionally given a subset T ⊆ V of vertices called terminals that need to be protected from fire. The objective is to minimize k - the maximum number of vertices to be saved at any time step, so that the fire does not spread to the vertices of T. The problem is hard to approximate up to any factor better than 2 even on trees. We show an O(log* n)-approximation LP-rounding algorithm for RMFC on trees. We also show that an even stronger LP relaxation has an integrality gap of Ω(log* n) on trees. Finally, we consider RMFC on directed layered graphs, and show an O(log n)-approximation LP-rounding algorithm, matching the integrality gap of the LP relaxation.