Complexity of Firefighting on Graphs
For graph theorists and algorithm designers, the paper establishes hardness results and bounds for a pursuit-evasion game, though the results are incremental.
The paper studies the firefighting game on graphs, providing almost sharp bounds for complete binary trees and proving that deciding the minimum number of firefighters is NP-hard. It also shows that shortest strategies can be superpolynomial in length.
We consider a pursuit-evasion game that describes the process of extinguishing a fire burning on the nodes of an undirected graph. We denote the minimum number of firefighters required by ffn(G) and provide almost sharp bounds to this graph parameter for complete binary trees. We show that deciding whether ffn(G) <= m for given G and m is NP-hard. Furthermore, we show that shortest strategies can have superpolynomial length, leaving open whether the problem is in NP. We provide a construction that allows for transferring these results to a well-established Cops and Robbers variant called the "Hunter and Rabbit game".