The firefighter problem: further steps in understanding its complexity

Janka Chlebikova, Morgan Chopin

Research output: Contribution to journalArticlepeer-review

73 Downloads (Pure)

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 [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, 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".

Original languageEnglish
Pages (from-to)42-51
Number of pages10
JournalTheoretical Computer Science
Volume676
Early online date18 Mar 2017
DOIs
Publication statusPublished - 9 May 2017

Keywords

  • firefighter problem
  • trees
  • pathwidth
  • cutwidth
  • bandwidth
  • parametrised complexity

Fingerprint

Dive into the research topics of 'The firefighter problem: further steps in understanding its complexity'. Together they form a unique fingerprint.

Cite this