Bazgan, Cristina Chopin, Morgan Ries, Bernard 2013 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)-Fire where b ≥ 2 firefighters are allowed at each time step and the objective is to maximize the number of saved vertices that belong to S. We also study the related decision problem (S, b)- Fire that asks whether all the vertices in S can be saved using b ≥ 2 firefighters at each time step. We show that (S, b)-Fire is NP-complete for trees of maximum degree b+2 even when S is the set of leaves. Using this last result, we prove the NP- hardness of Max (S, b)-Fire for trees of maximum degree b + 3 even when S is the set of all vertices. On the positive side, we give a polynomial-time algorithm for solving (S, b)-Fire and Max (S, b)-Fire on 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 the Max (S, b)-Fire problem (and the corresponding weighted version) for a subclass of trees, namely k-caterpillars. Finally, we observe that the minimization version of Max (S, b)-Fire is not n^(1−ε)-approximable on trees for any ϵ ∈ (0, 1) and b ≥ 1 if P≠ NP. application/pdf https://folia.unifr.ch/global/documents/308620 https://folia.unifr.ch/documents/308620/files/firefighter.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2012.11.011 info:eu-repo/semantics/openAccess License undefined Discrete Applied Mathematics. - 2013, vol. 161, p. 899-908 firefighter problem complexity approximation trees caterpillar info:eu-repo/classification/udc/004 The firefighter problem with more than one firefighter on trees http://purl.org/coar/resource_type/c_6501