Parameterized Complexity of Firefighting
Bazgan, Cristina; Chopin, Morgan; Cygan, Marek; Fellows, Michael R.; Fomin, Fedor V.; van Leeuwen, Erik Jan (2014), Parameterized Complexity of Firefighting, Journal of Computer and System Sciences, 80, 7, p. 1285-1297. http://dx.doi.org/10.1016/j.jcss.2014.03.001
TypeArticle accepté pour publication ou publié
Journal nameJournal of Computer and System Sciences
MetadataShow full item record
Fellows, Michael R.
Fomin, Fedor V.
van Leeuwen, Erik Jan
Abstract (EN)TheFirefighterproblem is to place firefighters on the vertices ofa graph to prevent a fire with known starting point from lighting upthe entire graph. In each time step, a firefighter may be placed on anunburned vertex, permanently protecting it, and the fire spreads toall neighboring unprotected vertices of burning vertices. The goal isto let as few vertices burn as possible. This problem is known to beNP-complete, even when restricted to trees of maximum degree three.Initial study showed theFirefighterproblem to be fixed-parametertractable on trees in various parameterizations. In this paper, wecon-sider a generalization of this problem, where at each time stepb≥1firefighters can be deployed. Our results answer several open questionsraised by Cai et al. . We show that this problem is W-hard whenparameterized by the number of saved vertices, protected vertices, andburned vertices. We also investigate several combined parameteriza-tions for which the problem is fixed-parameter tractable. Some of ouralgorithms improve on previously known algorithms. We also establishlower bounds to polynomial kernelization
Subjects / KeywordsFirefighter problem; Bipartite graphs
Showing items related by title and author.
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié