TY - GEN
T1 - The firefighter problem
T2 - 9th International Symposium, IPEC 2014
AU - Chlebikova, Janka
AU - Chopin, Morgan
PY - 2014/12/3
Y1 - 2014/12/3
N2 - 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”.
AB - 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”.
U2 - 10.1007/978-3-319-13524-3_15
DO - 10.1007/978-3-319-13524-3_15
M3 - Conference contribution
SN - 9783319135236
T3 - Lecture Notes in Computer Science
SP - 172
EP - 183
BT - Parameterized and Exact Computation
A2 - Cygan, Mareck
A2 - Heggernes, Pinar
PB - Springer
Y2 - 10 September 2014 through 12 September 2014
ER -