Thumbnail - Request a copy

Parameterized Complexity of the Firefighter Problem

Bazgan, Cristina; Chopin, Morgan; Fellows, Michael R. (2011), Parameterized Complexity of the Firefighter Problem, in Watanabe, Osamu, ISAAC 2011, Springer : Berlin Heidelberg, p. 643-652

Type
Communication / Conférence
Date
2011
Conference country
JAPAN
Book title
ISAAC 2011
Book author
Watanabe, Osamu
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-25590-8
Pages
643-652
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Chopin, Morgan
Fellows, Michael R.
Abstract (EN)
In this paper we study the parameterized complexity of the firefighter problem. More precisely, 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.
Subjects / Keywords
bipartite graphs; trees; Firefighter problem; vertex