An extension of the firefighter problem with vertex values and defence budget

Abstract

Let G be an undirected graph with node set V and edge set E, F be a subset of vertices, and d be a given number of defenders. In the Firefighter game, a fire breaks out on all vertices in F at time zero. At each subsequent time step, the d defenders can protect one vertex eachfrom catching fire. Then, the fire spreads from each burning vertex to every adjacent vertexthat is neither burning nor defended. The game ends when the fire can no longer spread.The goal is to find a defence strategy that minimizes the number of burning vertices. In thiswork, we relax the classical assumptions that all vertices have uniform values and costs,i.e., we allow vertices to have different values and costs for being defended. Furthermore,instead of d defenders we are given a defence budget that we can spend each time step todefend the vertices. We present a mixed integer programming formulation for this problem,along with some valid inequalities and bounds on the maximal duration of the game.