We consider the Resource Minimization Fire Containment problem (RMFC): Given a graph G=(V,E) with source vertex s where the fire starts and a subset T of vertices that need to be protected from the fire. At each time step, firefighters can save up to k vertices, while the fire spreads from burning vertices to all their neighbors that have not been saved so far. The goal is to minimize k -- the number of firefighters -- while ensuring that no vertices in T burn. This model has been used to abstract the spread mechanism of fire and perfectly contagious diseases. In this talk, we show an O(log* n)-approximation LP-rounding algorithm for RMFC on trees, with a matching lower bound on the integrality gap of the LP.

(Joint work with Julia Chuzhoy)