Abstract (EN)

In this paper we study the complexity of generalized versions of the firefighter problem on trees, and answer several open questions of Finbow and MacGillivray (2009) [8]. More specifically, we consider the version denoted by Max(S,b)(S,b)-Fire where b≥2b≥2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to SS. We also study the related decision problem (S,b)(S,b)-Fire that asks whether all the vertices in SS can be saved using b≥2b≥2 firefighters at each time step.We show that (S,b)(S,b)-Fire is NP-complete for trees of maximum degree b+2b+2 even when SS is the set of leaves. Using this last result, we prove the NP-hardness of Max(S,b)(S,b)-Fire for trees of maximum degree b+3b+3 even when SS is the set of all vertices. On the positive side, we give a polynomial-time algorithm for solving (S,b)(S,b)-Fire and Max(S,b)(S,b)-Fire on trees of maximum degree b+2b+2 when the fire breaks out at a vertex of degree at most b+1b+1. Moreover, we present a polynomial-time algorithm for the Max(S,b)(S,b)-Fire problem (and the corresponding weighted version) for a subclass of trees, namely kk-caterpillars. Finally, we observe that the minimization version of Max(S,b)(S,b)-Fire is not n1−εn1−ε-approximable on trees for any ϵ∈(0,1)ϵ∈(0,1) and b≥1b≥1 if P≠NPP≠NP.