Slash and burn on graphs — Firefighting with general weights

In Hartnell’s firefighter game a player tries to contain a fire breaking out at some vertex of a graph and spreading in rounds from burned vertices to their neighbors, by defending one vertex in each round, which will remain protected from the fire throughout the rest of the game. The objective of the player is to save as many vertices as possible from burning.Here we study a generalization for weighted graphs, where the weights can be positive as well as negative. The objective of the player is to maximize the total weight of the saved vertices of positive weight minus the total weight of the burned vertices of negative weight, that is, the player should save vertices of positive weight and let vertices of negative weight burn. We prove that this maximization problem is already hard for binary trees and describe two greedy approximation algorithms for trees. Furthermore, we discuss a weighted version of the surviving rate.