The Firefighter Problem: A Structural Analysis

DOI10.1007/978-3-319-13524-3_15zbMATH Open1457.68124arXiv1310.2322OpenAlexW2964351140MaRDI QIDQ2946017FDOQ2946017

Authors: Janka Chlebíková, Morgan Chopin 

Publication date: 15 September 2015

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

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.

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

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

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)

Cites Work

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

Cited In (9)

• Surviving rate of graphs and firefighter problem
• New integrality gap results for the firefighters problem on trees
• Title not available (Why is that?)
• 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)