Algorithmics and Computational Complexity Research GroupTalk 12.04.2012

## 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