A graph theoretical approach to the firebreak locating problem

• Published in: Theoretical computer science 2022-05, Vol.914, p.47-72
• Main Authors: Demange, Marc, Di Fonso, Alessia, Di Stefano, Gabriele, Vittorini, Pierpaolo
• Format: Article
• Language: English
• Subjects: Firebreak location; NP-hardness; Planar graphs; Restricted Planar Max 2-SAT; Risk management; Wildfire emergency management
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2022.02.012

In the last decade, wildfires have become wider and more destructive. Climate change and the growth of urban areas are among the main factors that increase the risk of large-scale fires. This risk can be lowered with preventive measures. Among them, firefighting lines are used to stop the fire spread and to offer a safe corridor where firefighting resources can be deployed. Due to their high cost of installation and maintenance, the placement of these lines must be carefully planned. In this work, we address this problem from a theoretical perspective. The land is modeled by a mixed graph in which vertices represent areas subject to burn while edges model the possibility of fire spreading from one area to another. Vertices are associated with probabilities of ignition and edges with probabilities of spread. We consider the problem of positioning firefighting lines such that the risk is reduced under a budget constraint. We call this problem Firebreak Location. We study its complexity and prove in particular its NP-hardness even when the graph is planar, bipartite, with a maximum degree four and the probabilities of propagation are equal to one. Planarity and low degree are indeed natural properties of real instances. We also show an efficient polynomial time algorithm for particular instances on trees.