2011/10/03 by Cristina Bazgan, Morgan Chopin, Bazgan, Cristina +3
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Opinion Dynamics and Social Influence
paper · doi:10.48550/arxiv.1110.0341
openalex publication_date 2011/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study the complexity of the firefighter problem and related problems on trees when more than one firefighter is available at each time step, and answer several open questions of Finbow and MacGillivray 2009. More precisely, when b ≥ 2 firefighters are allowed at each time step, the problem is NP-complete for trees of maximum degree b+2 and polynomial-time solvable for trees of maximum degree b+2 when the fire breaks out at a vertex of degree at most b+1. Moreover we present a polynomial-time algorithm for a subclass of trees, namely k-caterpillars.