The firefighter problem: a structural analysis

Janka Chlebikova, Morgan Chopin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

143 Downloads (Pure)

Abstract

We consider the complexity of the firefighter problem where a budget of b ≥1 firefighters are available at each time step. This problem is proved to be NP-complete even on trees of degree at most three and b = 1 [S. Finbow, A. King, G. MacGillivray, and R. Rizzi. The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307(16), 2094–2105, 2007] and on trees of bounded degree b+3 for any fixed b ≥2 [C. Bazgan, M. Chopin, and B. Ries. The firefighter problem with more than one firefighter on trees. Discrete Applied Mathematics, 161(7-8), 899–908, 2013]. In this paper, we provide further insight into the complexity landscape of the problem by showing a complexity dichotomy result with respect to the parameters pathwidth and maximum degree of the input graph. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any b ≥1. Then we show that the problem turns out to be fixed parameter-tractable with respect to the combined parameter “pathwidth” and “maximum degree” of the input graph. Finally, we show that the problem remains NP-complete on very dense graphs, namely co-bipartite graphs, but is fixed-parameter tractable with respect to the parameter “cluster vertex deletion”.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
Subtitle of host publication9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers
EditorsMareck Cygan, Pinar Heggernes
PublisherSpringer
Chapter15
Pages172-183
Number of pages12
ISBN (Electronic)9783319135243
ISBN (Print)9783319135236
DOIs
Publication statusPublished - 3 Dec 2014
Event9th International Symposium, IPEC 2014 - Wroclaw, Poland
Duration: 10 Sep 201412 Sep 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8894
ISSN (Print)0302-9743

Other

Other9th International Symposium, IPEC 2014
Country/TerritoryPoland
CityWroclaw
Period10/09/1412/09/14

Fingerprint

Dive into the research topics of 'The firefighter problem: a structural analysis'. Together they form a unique fingerprint.

Cite this