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 -