The firefighter problem for cubic graphs

We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2010-02, Vol.310 (3), p.614-621
Main Authors: King, Andrew, MacGillivray, Gary
Format: Article
Language:English
Subjects:
Algebra
Combinatorics
Combinatorics. Ordered structures
Dichotomy theorem
Exact sciences and technology
Firefighter problem
Graph theory
Mathematical analysis
Mathematics
Ordinary differential equations
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2009.05.007