### Inhalt des Dokuments

## Parameterized complexity of the Firefighter problem

**Morgan Chopin (Ph.D. Student University Paris-Dauphine)**

We study the parameterized complexity of the following generalization of the firefighter problem. Initially, a fire breaks out at some special vertex s of a graph. At each time step, we have to choose b vertices which will be protected by firefighters. Then the fire spreads to all unprotected neighbors of the vertices on fire. The process ends when the fire can no longer spread, and then all vertices that are not on fire are considered as saved. The Saving k-Vertices (resp. Saving All But k-Vertices) problem asks to find a placement strategy of the firefighters to save at least k (resp. to burn at most k) vertices.We study the parameterized complexity of the following generalization of the firefighter problem. Initially, a fire breaks out at some special vertex s of a graph. At each time step, we have to choose b vertices which will be protected by firefighters. Then the fire spreads to all unprotected neighbors of the vertices on fire. The process ends when the fire can no longer spread, and then all vertices that are not on fire are considered as saved. The Saving k-Vertices (resp. Saving All But k-Vertices) problem asks to find a placement strategy of the firefighters to save at least k (resp. to burn at most k) vertices.

We show that Saving k-Vertices and its dual Saving All But k-Vertices are both W[1]-hard for parameter k even for bipartite graphs. We also investigate several cases for which the firefighter problem is tractable. For instance, Saving k-Vertices is fixed-parameter tractable on planar graphs for parameter k. Moreover, we prove a lower bound to polynomial kernelization for Saving All But k-Vertices.

Date | Speaker | Location | Language |
---|---|---|---|

12.04.2012 16:00 | Morgan Chopin | FR 6510 | english |