The firefighter problem with more than one firefighter on trees
Published in:
 Discrete Applied Mathematics.  2013, vol. 161, p. 899908
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 NPcomplete 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 polynomialtime 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 polynomialtime algorithm for the Max (S, b)Fire problem (and the corresponding weighted version) for a subclass of trees, namely kcaterpillars. 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


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/308620
Statistics
Document views: 18
File downloads: