The Firefighter Problem: A Structural Analysis

DOI10.1007/978-3-319-13524-3_15MaRDI QIDQ2946017zbMATH OpenOpenAlexFDO

Authors Janka Chlebíková, Morgan Chopin

Publication date 15 September 2015

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.2322

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: We consider the complexity of the firefighter problem where b>=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>=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>=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.

Recommendations

• The firefighter problem: further steps in understanding its complexity
• The Firefighter problem: a survey of results, directions and questions
• An analysis of the weighted firefighter problem
• scientific article; zbMATH DE number 2061798
• A matheuristic for the firefighter problem on graphs
• Parameterized complexity of the firefighter problem
• Finding exact solutions for the geometric firefighter problem in practice

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• A generalization of the firefighter problem on \(\mathbb Z \times \mathbb Z\)
• Approximability of the firefighter problem. Computing cuts over time
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Fire containment in grids of dimension three and higher
• Firefighting on Trees: (1 − 1/e)–Approximation, Fixed Parameter Tractability and a Subexponential Algorithm
• Firefighting on trees: How bad is the greedy algorithm?
• Graphs with small bandwidth and cutwidth
• More fires and more fighters
• Parameterized complexity of firefighting
• The firefighter problem for cubic graphs
• The firefighter problem for graphs of maximum degree three
• The firefighter problem with more than one firefighter on trees
• Tree-width, path-width, and cutwidth

Cited in

(9)

• Surviving rate of graphs and firefighter problem
• New integrality gap results for the firefighters problem on trees
• scientific article; zbMATH DE number 2061798 (Why is no real title available?)
• Firefighting as a strategic game
• The firebreak problem
• The firefighter problem with more than one firefighter on trees
• The firefighter problem on graph classes
• The firefighter problem for graphs of maximum degree three
• The firefighter problem: further steps in understanding its complexity

This page was built for publication: The Firefighter Problem: A Structural Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946017)