Parameterized complexity of the firefighter problem

Cristina Bazgan; Morgan Chopin; Michael Fellows

doi:10.1007/978-3-642-25591-5_66

Parameterized complexity of the firefighter problem

Cristina Bazgan, Morgan Chopin, Michael Fellows

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 22nd International Symposium on Algorithms and Computation
Editors	Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, Osamu Watanabe
Place of Publication	Germany
Publisher	Springer
Pages	643-652
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-25591-5_66
Publication status	Published - 2011
Event	International Symposium on Algorithms and Computation (ISAAC 2011 22nd) - Japan, Japan Duration: 5 Dec 2011 → 8 Dec 2011 Conference number: 2011 (22nd)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7074
ISSN (Print)	0302-9743

Conference

Conference	International Symposium on Algorithms and Computation (ISAAC 2011 22nd)
Abbreviated title	ISAAC
Country/Territory	Japan
Period	5/12/11 → 8/12/11

Access to Document

10.1007/978-3-642-25591-5_66

Cite this

@inproceedings{b9909458a2814183af758fefe4a9b737,

title = "Parameterized complexity of the firefighter problem",

abstract = "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.",

keywords = "Bipartite graphs, Kernelization, Lower bounds, Parameterized complexity, Planar graph, Algorithms, Fire extinguishers, Graph theory",

author = "Cristina Bazgan and Morgan Chopin and Michael Fellows",

year = "2011",

doi = "10.1007/978-3-642-25591-5_66",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "643--652",

editor = "Takao Asano and Shin-ichi Nakano and Yoshio Okamoto and Osamu Watanabe",

booktitle = "Proceedings of the 22nd International Symposium on Algorithms and Computation",

address = "Switzerland",

note = "International Symposium on Algorithms and Computation (ISAAC 2011 22nd), ISAAC ; Conference date: 05-12-2011 Through 08-12-2011",

}

Bazgan, C, Chopin, M & Fellows, M 2011, Parameterized complexity of the firefighter problem. in T Asano, S Nakano, Y Okamoto & O Watanabe (eds), Proceedings of the 22nd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7074, Springer, Germany, pp. 643-652, International Symposium on Algorithms and Computation (ISAAC 2011 22nd), Japan, 5/12/11. https://doi.org/10.1007/978-3-642-25591-5_66

Parameterized complexity of the firefighter problem. / Bazgan, Cristina; Chopin, Morgan; Fellows, Michael.
Proceedings of the 22nd International Symposium on Algorithms and Computation. ed. / Takao Asano; Shin-ichi Nakano; Yoshio Okamoto; Osamu Watanabe. Germany: Springer, 2011. p. 643-652 (Lecture Notes in Computer Science; Vol. 7074).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-review

TY - GEN

T1 - Parameterized complexity of the firefighter problem

AU - Bazgan, Cristina

AU - Chopin, Morgan

AU - Fellows, Michael

N1 - Conference code: 2011 (22nd)

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Bipartite graphs

KW - Kernelization

KW - Lower bounds

KW - Parameterized complexity

KW - Planar graph

KW - Algorithms

KW - Fire extinguishers

KW - Graph theory

U2 - 10.1007/978-3-642-25591-5_66

DO - 10.1007/978-3-642-25591-5_66

M3 - Conference Paper published in Proceedings

T3 - Lecture Notes in Computer Science

SP - 643

EP - 652

BT - Proceedings of the 22nd International Symposium on Algorithms and Computation

A2 - Asano, Takao

A2 - Nakano, Shin-ichi

A2 - Okamoto, Yoshio

A2 - Watanabe, Osamu

PB - Springer

CY - Germany

T2 - International Symposium on Algorithms and Computation (ISAAC 2011 22nd)

Y2 - 5 December 2011 through 8 December 2011

ER -

Parameterized complexity of the firefighter problem

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this