Burning a Graph is Hard

2015/11/20 by Anthony Bonato, Bonato, Anthony, Jeannette Janssen +3 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1511.06774

20 Pages, 4 figures, presented at GRASTA-MAC 2015 (October 19-23rd, 2015, Montréal, Canada)

arxiv created 2015/11/20 · openalex publication_date 2015/11/20 · arxiv updated 2015/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• How to burn a graph

Cited by

• Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
• Between burning and cooling: liminal burning on graphs
• Extremal Trees With Prescribed Burning Numbers

Related

• Graph Burning: Tight Bounds on the Burning Numbers of Path Forests and Spiders
• Bounds on the burning numbers of spiders and path-forests
• Burning Geometric Graphs
• New heuristics for burning graphs
• Approximation Algorithms for Graph Burning