Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Parameterized complexity of firefighting

Bazgan, Cristina, Chopin, Morgan, Cygan, Marek, Fellows, Michael R., Fomin, Fedor V. and van Leeuwen, Erik Jan (2014). Parameterized complexity of firefighting. Journal of Computer and System Sciences,80(7):1285-1297.

Document type: Journal Article
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article

Google Scholar Search Google Scholar

IRMA ID 75039815xPUB312
Title Parameterized complexity of firefighting
Author Bazgan, Cristina
Chopin, Morgan
Cygan, Marek
Fellows, Michael R.
Fomin, Fedor V.
van Leeuwen, Erik Jan
Journal Name Journal of Computer and System Sciences
Publication Date 2014
Volume Number 80
Issue Number 7
ISSN 0022-0000   (check CDU catalogue  open catalogue search in new window)
Scopus ID 2-s2.0-84901761766
Start Page 1285
End Page 1297
Total Pages 13
Place of Publication United States
Publisher Academic Press
HERDC Category C1 - Journal Article (DIISR)
Abstract The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b⩾1b⩾1 firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.
Keywords Firefighter problem
Fixed parameter tractability
Kernelization
DOI http://dx.doi.org/10.1016/j.jcss.2014.03.001   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 7 Abstract Views  -  Detailed Statistics
Created: Wed, 19 Aug 2015, 12:03:08 CST