Firefighting on trees (Q2328866): Difference between revisions

\textit{B. Hartnell} and \textit{Q. Li} [Congr. Numerantium 145, 187--192 (2000; Zbl 0974.68005)] introduced the firefighting problem. It is a deterministic discrete-time one-player game defined on a graph. Fire breaks out first on a vertex and at each step, if not blocked, spreads to all adjacent vertices. To contain it, the player is given a number $f_i$ of firefighters at each turn $i$ and can use them to safeguard vertices which are neither burning nor already protected. The game gets over when it cannot spread any further. In the case of finite graphs the goal is to save as many vertices as possible, while in the infinite case, the player wins if the game finishes, which means that the fire is contained. A very natural relaxed version of this game is when the amount of firefighters available at each turn is any non-negative number and the amount allocated to vertices lies between 0 and 1. A vertex with a protection less than 1 is partially protected and its unprotected part can burn partially and transmit only its fraction of fire to the adjacent vertices. So, the $f_i$ may take any non-negative value. This defines a variant game called fractional firefighter which was introduced P. Fogarty in 2003. The authors in this paper introduce an online version of both firefighter and fractional firefighter where the sequence of firefighters is revealed over time (online) while the graph, a tree is known from the beginning. First they generalize an analysis of a greedy algorithm known only in special cases of firefighter to fractional firefighter. Then they improved competitive algorithms for online firefighter with a small total number of firefighters while establishing that the greedy approach is optimal in the general case. Then they deal with the infinite case. By considering the class of spherically symmetric trees where all vertices at the same level have the same degree, They express the separation problem as a purely numerical one-player game, and called it the targeting game. They give two sufficient conditions for the existence of a winning strategy. Finally they establish sufficient conditions for containing the fire expressed as asymptotic comparisons of the number of available firefighters and the size of the levels in the tree. In the online case, for a particular class of trees the level size of which grows linearly, the authors give a sufficient condition to contain the fire. They conclude by observing that the question of approximating (fractional) firefighter in finite trees for a general firefighter sequence is a pertinent area of research that remains uninvestigated. The proof of all the results in this paper are mind blowing and very deep.