[2603.29865] Wildfire Suppression: Complexity, Models, and Instances

Computer Science > Computational Engineering, Finance, and Science arXiv:2603.29865 (cs) [Submitted on 17 Jan 2026] Title:Wildfire Suppression: Complexity, Models, and Instances Authors:Gustavo Delazeri, Marcus Ritt View a PDF of the paper titled Wildfire Suppression: Complexity, Models, and Instances, by Gustavo Delazeri and Marcus Ritt View PDF HTML (experimental) Abstract:Wildfires cause major losses worldwide, and the frequency of fire-weather conditions is likely to increase in many regions. We study the allocation of suppression resources over time on a graph-based representation of a landscape to slow down fire propagation. Our contributions are theoretical and methodological. First, we prove that this problem and related variants in the literature are NP-complete, including cases without resource-timing constraints. Second, we propose a new mixed-integer programming (MIP) formulation that obtains state-of-the-art results, showing that MIP is a competitive approach contrary to earlier findings. Third, showing that existing benchmarks lack realism and difficulty, we introduce a physics-grounded instance generator based on Rothermel's surface fire spread model. We use these diverse instances to benchmark the literature, identifying the specific conditions where each algorithm succeeds or fails. Subjects: Computational Engineering, Finance, and Science (cs.CE); Artificial Intelligence (cs.AI) Cite as: arXiv:2603.29865 [cs.CE]   (or arXiv:2603.29865v1 [cs.CE] for this v...