Premium
The Firefighter problem: Saving sets of vertices on cubic graphs
Author(s) -
Duffy Christopher,
MacGillivray Gary
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21873
Subject(s) - combinatorics , vertex (graph theory) , degree (music) , graph , mathematics , context (archaeology) , computer science , independent set , set (abstract data type) , discrete mathematics , physics , geography , archaeology , acoustics , programming language
In the context of the Firefighter problem, a deterministic model of the spread of a fire or virus on a graph, SFIRE is the decision problem that asks if a specified set of vertices can be prevented from burning. We show SFIRE remains NP‐complete even when restricted to graphs with maximum degree 3 even when the fire starts at a vertex of degree 2.