Burning a graph is hard

被引：48

作者：

Bessy, Stephane ^{[1
]}

Bonato, Anthony ^{[2
]}

Janssen, Jeannette ^{[3
]}

Rautenbach, Dieter ^{[4
]}

Roshanbin, Elham ^{[3
]}

机构：

[1] LIRMM, Montpellier, France

[2] Ryerson Univ, Dept Math, Toronto, ON M5B 2K3, Canada

[3] Dalhousie Univ, Dept Math & Stat, Halifax, NS B3H 3J5, Canada

[4] Ulm Univ, Inst Optimizat & Operat Res, Ulm, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 232卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Graph burning; Computational complexity; NP-complete; 3-partition; Polynomial time algorithm; Approximation algorithm; FIREFIGHTER PROBLEM;

D O I：

10.1016/j.dam.2017.07.016

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is NP-complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path forests if the number of arms and components, respectively, are fixed. Finally, we describe a polynomial time approximation algorithm with approximation factor 3 for general graphs. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：73 / 87

页数：15

共 22 条

[11] The firefighter problem for graphs of maximum degree three [J].