The Moving Firefighter Problem

Abstract

The original formulation of the firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G. At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless they are defended by a firefighter that can move between any pair of vertices in a single time unit. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread. In this work, we present the moving firefighter problem, which is a generalization of the firefighter problem where the time it takes a firefighter to move from a vertex u to defend vertex v is determined by a function τ. This new formulation models situations such as a wildfire or a flood, where firefighters have to physically move from their current position to the location of an entity they intend to defend. It also incorporates the notion that entities modeled by the vertices are not necessarily instantaneously defended upon the arrival of a firefighter. We present a mixed-integer quadratically constrained program (MIQCP) for the optimization version of the moving firefighter problem that minimizes the number of burnt vertices for the case of general finite graphs, an arbitrary set F⊂V of vertices where the fire breaks out, a single firefighter, and metric time functions τ.

Keywords

• firefighter problem
• np-hard
• mathematical programming
• mixed-integer quadratically constrained programming (MIQCP)
• exact algorithm
• spread and containment in networks