The firefighter problem is a monotone dynamic process in graphs that can be viewed as modeling the use of a limited supply of vaccinations to stop the spread of an epidemic. In more detail, a fire spreads through a graph, from burning vertices to their unprotected neighbors. In every round, a small amount of unburnt vertices can be protected by firefighters. How many firefighters per turn, on average, are needed to stop the fire from advancing? We prove tight lower and upper bounds on the amount of firefighters needed to control a fire in the Cartesian planar grid and in the strong planar grid, resolving two conjectures of Ng and Raff.
The firefighter problem is loosely connected with Conway's angel problem @cite_7 . This is a game of pursuit in @math , in which the angel can move to any point within @math -distance @math and the devil can destroy one unoccupied point per turn, bearing similarities to the @math case of the firefighter problem. The two main differences between the angel problem and the firefighter problem are The fire is , that is, it needs not choose its path in advance; The firefighters play a strategy, that is, they cannot adapt their strategy to the fire's advancement. It is known that for @math , where the fractional version is defined appropriately, the devil wins @cite_5 , and that for @math the angel wins @cite_6 @cite_13 @cite_3 @cite_14 . Our results, when presented as a variant of the angel problem in which the fire is more powerful, show that the threshold is @math instead of @math .
@cite_14 @cite_7 @cite_3 @cite_6 @cite_5 @cite_13
2166602752 2106768299 2070582302 1964535518
We solve Conway's Angel Problem by showing that the Angel of power 2 has a winning strategy. An old observation of Conway is that we may suppose without loss of generality that the Angel never jumps to a square where he could have already landed at a previous time. We turn this observation around and prove that we may suppose without loss of generality that the Devil never eats a square where the Angel could have already jumped. Then we give a simple winning strategy for the Angel. We show that in the game of angel and devil, played on the planar integer lattice, the angel of power 4 can evade the devil. This answers a question of Berlekamp, Conway and Guy. Independent proofs that work for the angel of power 2 have been given by Kloster and by Mathe. We solve the Angel Problem, by describing a strategy that guarantees the win of an Angel of power 2 or greater. Basically, the Angel should move north as quickly as possible. However, he should detour around eaten squares, as long as the extra distance does not exceed twice the number of eaten squares evaded. We show that an Angel following this strategy will always spot a trap early enough to avoid it. A token located at some vertex @math of a connected, undirected graph G on n vertices is said to be taking a “random walk” on G if, whenever it is instructed to move, it moves with equal probability to any of the neighbors of @math . The authors consider the following problem: Suppose that two tokens are placed on G, and at each tick of the clock a certain demon decides which of them is to make the next move. The demon is trying to keep the tokens apart as long as possible. What is the expected time M before they meet?The problem arises in the study of self-stabilizing systems, a topic of recent interest in distributed computing. Since previous upper bounds for M were exponential in n, the issue was to obtain a polynomial bound. The authors use a novel potential function argument to show that in the worst case @math .