Contents

An Analysis of the Weighted Firefighter Problem

Christopher Duffy1, Gary Macgillivray2
1Department of Mathematics and Statistics, University of Victoria, Canada
2Department Of Mathematics and Statistics, University of Victoria, Canada

Abstract

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.