Parameterized complexity of firefighting

作者：

Highlights：

• We study a generalization of the firefighter problem with b firefighters at each step.

• W[1]-hardness on bipartite graphs.

• Improved algorithms on trees.

• FPT results for bounded treewidth and planar graphs.

• No polynomial kernel on trees.

摘要

•We study a generalization of the firefighter problem with b firefighters at each step.•W[1]-hardness on bipartite graphs.•Improved algorithms on trees.•FPT results for bounded treewidth and planar graphs.•No polynomial kernel on trees.

论文关键词：Firefighter problem,Fixed parameter tractability,Kernelization

论文评审过程：Received 24 November 2011, Revised 31 January 2014, Accepted 3 March 2014, Available online 15 March 2014.

论文官网地址：https://doi.org/10.1016/j.jcss.2014.03.001