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

M. Baldomero Naranjo, J. Kalcsics, A. M. Rodríguez Chía, C. Wedderburn

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 each from catching fire. Then, the fire spreads from each burning vertex to every adjacent vertex that 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 this work, 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 to defend 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.

Keywords: Firefighter, Location, Mixed Integer Programming

GT12.GELOCA1 Invited Session
November 9, 2023  4:50 PM
HC2: Canónigos Room 2

M. Albareda Sambola, M. Landete, G. Laporte

M. Merino Maestre, I. Gago Carro, U. Aldasoro Marcellan, J. Ceberio Uribe

J. Puerto Albandoz