In many practical situations, we have a graph of spatial locations in which, at each moment in time, a harmful process, such as an epidemic or fire, spreads from a node to its neighbor, unless this neighbor has been protected earlier (vaccinated). Usually, our resources are limited, such that at any particular moment, we can only protect B nodes. The direct problem is selecting a set of B nodes so as to minimize the final damage. A dual problem is when we have a list of nodes that need to be protected, and we want to find the smallest budget B to achieve such protection.

An interesting variation of these problems describes the “spreading” of harmful ideas. Here, protection consists of introducing a beneficial idea, so that the beneficial idea also spreads from a node to its neighbor, thus automatically enlarging the set of protected nodes.

Both nonspreading and spreading versions of this “firefighter” problem are known to be nondeterministic polynomial time (NP)-hard, so the paper looks for feasible suboptimal algorithms. The best results are possible for the direct spreading problem, for which we can compute a solution that is optimal up to the factor of 1 - 1/e. For the nonspreading version, the problem of finding optimal locations is proven to be NP-hard, even to approximate; however, the problem of minimizing the budget can be reasonably approximated, although with a less spectacular factor than in the direct spreading case.