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érenceDate
2011Conference country
JAPANBook title
ISAAC 2011Book author
Watanabe, OsamuPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-25590-8
Pages
643-652
Metadata
Show full item recordAbstract (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; vertexRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan (2012) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan (2014) Article accepté pour publication ou publié