Back to Search
Start Over
The firefighter problem: Further steps in understanding its complexity.
- Source :
-
Theoretical Computer Science . May2017, Vol. 676, p42-51. 10p. - Publication Year :
- 2017
-
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 known to be NP-complete even on trees of degree at most three and b = 1 [14] and on trees of bounded degree ( b + 3 ) for any fixed b ≥ 2 [4] . 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, first, we 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”. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 676
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 122646193
- Full Text :
- https://doi.org/10.1016/j.tcs.2017.03.004