Continuous Firefighting on Infinite Square Grids

摘要

The classical firefighter problem, introduced by Bert Hartnell in 1995, is a deterministic discrete-time model of the spread and defence of fire, rumor, or disease. In contrast to the generally "discontinuous" firefighter movements of the classical setting, we propose in the paper the continuous firefighting model. Given an undirected graph G, at time 0, all vertices of G are undefended, and fires break out on one or multiple different vertices of G. At each subsequent time step, the fire spreads from each burning vertex to all of its undefended neighbors. A finite number of firefighters are available to be assigned on some vertices of G at time 1, and each firefighter can only move from his current location (vertex) to one of his neighbors or stay still at each time step. A vertex is defended if some firefighter reaches it no later than the fire. We study fire containment on infinite k-dimensional square grids under the continuous firefighting model. We show that the minimum number of firefighters needed is exactly 2k for single fire, and 5 for multiple fires when k = 2.