The firefighter problem with more than one firefighter on trees
- Bazgan, Cristina Université Paris-Dauphine, France
- Chopin, Morgan Université Paris-Dauphine, France
- Ries, Bernard Université Paris-Dauphine, France
-
2013
Published in:
- Discrete Applied Mathematics. - 2013, vol. 161, p. 899-908
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 328826
- DOI 10.1016/j.dam.2012.11.011
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308620
Statistics
Document views: 35
File downloads:
- firefighter.pdf: 34