Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-162 | 28th April 2014 09:49

The Firefighter Problem: A Structural Analysis

RSS-Feed




Revision #1
Authors: Janka Chlebíková, Morgan Chopin
Accepted on: 28th April 2014 09:49
Downloads: 423
Keywords: 


Abstract:

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget $b \geq 2$ (Bazgan et al. 2012).
In this paper, we provide further insight into the complexity landscape of the problem by showing that the pathwidth and the maximum degree of the input graph govern its complexity. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any fixed budget $b \geq 1$. We then 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.


Paper:

TR13-162 | 1st October 2013 12:40

The Firefighter Problem: A Structural Analysis





TR13-162
Authors: Janka Chlebíková, Morgan Chopin
Publication: 22nd November 2013 12:11
Downloads: 753
Keywords: 


Abstract:

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget $b \geq 2$ (Bazgan et al. 2012).
In this paper, we provide further insight into the complexity landscape of the problem by showing that the pathwidth and the maximum degree of a graph govern the complexity of the problem. More precisely, we first prove that the problem is NP-complete even on trees of pathwidth at most three for any fixed budget $b \geq 1$. We then 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.



ISSN 1433-8092 | Imprint