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 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 1995, P 25 MAN C COMB MATH

[3]

[Anonymous], P 32 INT C AUT LANG

[4] Graph bootstrap percolation [J].

Balogh, Jozsef ;

Bollobas, Bela ;

Morris, Robert .

RANDOM STRUCTURES & ALGORITHMS, 2012, 41 (04) :413-440

[5]

Bessy S., 2016, BOUNDS BURNING UNPUB

[6]

Bessy S., 2015, ARXIV151106023

[7]

Bonato A., 2015, ARXIV151106774

[8]

Bonato A., 2011, The Game of Cops and Robbers on Graphs

[9] How to Burn a Graph [J].

Bonato, Anthony ;

Janssen, Jeannette ;

Roshanbin, Elham .

INTERNET MATHEMATICS, 2016, 12 (1-2) :85-100

[10]

Domingos P., 2001, KDD-2001. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, P57, DOI 10.1145/502512.502525

← 1 2 3 →