An Analysis of the Weighted Firefighter Problem

For the Firefighter Process with weights on the vertices, we show that the problem of deciding whether a subset of vertices of a total weight can be saved from burning remains NP-complete when restricted to binary trees. In addition, we show that a greedy algorithm that defends the vertex of highest degree adjacent to a burning vertex is not an \(\epsilon\)-\emph{approximation} algorithm for any \(\epsilon \in (0, 1]\) for the problem of determining the maximum weight that can be saved. This closes an open problem posed by MacGillivray and Wang.