The Firefighter problem was introduced by Hartnell (1995) as a natural model for optimal inhibition of harmful spreading phenomena on a graph. Despite considerable interest in the problem and progress on several fronts, our understanding of how well this and related problems can be approximated is still very limited. Interestingly, this is even true when the underlying graph is a spanning trees, which is one of the most-studied graph structures in this context.
The Firefighter problem on trees is defined as follows. We are given a graph $G=(V,E)$ which is a spanning tree and a vertex $r\in V$, called \emph{root}. The problem is defined over discretized time steps. At time $0$, a fire starts at $r$ and spreads step by step to neighboring vertices. During each time step $1,2,\dots$, an arbitrary non-burning $v$ vertex can be protected, which prevents $v$ from burning in all future time steps. The goal is to find a protection strategy that maximizes the number of vertices that will not burn. A closely related problem, called Resource Minimization for Fire Containment (RMFC) on trees, was introduced by Chalermsook and Chuzhoy (2010). Here the task is to determine the smallest number $B\in \mathbb{Z}_{>0}$ such that if one can protect $B$ vertices at each time step (instead of just $1$), then there is a protection strategy such that none of the leaves of the tree will catch fire.
The best known approximation algorithms for Firefighter and RMFC are $1-1/e$ (Cai, Verbin and Yang, 2008) and $\log^* n$ (Chalermsook and Chuzhoy, 2010), respectively. These algorithms are based on rounding of natural LP relaxations of the respective problems, for which matching integrality gap lower bounds are also proved. In this paper we show efficient algorithms with significantly better approximation ratios, thus showing that these bounds do not reflect the approximability thresholds of these problems. Concretely, we present a polynomial time approximation scheme (PTAS) for the Firefighter problem and an $O(1)$-approximation for RMFC, essentially matching the existing hardness results for the respective problems. To arrive at these results we use the natural LP relaxations for the respective problems in combination with various new techniques to go around the problem of large integrality gaps.
Joint work with David Adjiashvili and Rico Zenklusen. |