Burning a graph is hard

作者：Bessy Stephane; Bonato Anthony; Janssen Jeannette; Rautenbach Dieter; Roshanbin Elham^*

来源：Discrete Applied Mathematics, 2017, 232: 73-87.

DOI：10.1016/j.dam.2017.07.016

• Graph burning
• Computational complexity
• NP-complete
• 3-partition
• Polynomial time algorithm
• Approximation algorithm

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.

• 出版日期2017-12-11