Advertisement
Published in:
2014 | OriginalPaper | Chapter
The Firefighter Problem: A Structural Analysis
Authors : Janka Chlebíková, Morgan Chopin
Published in: Parameterized and Exact Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider the complexity of the firefighter problem where a budget of \({b \ge 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}\) [10] and on trees of bounded degree \(b+3\) for any fixed \(b \ge 2\) [3]. 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 \ge 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”.