Hardness of Burning Number Problem on Regular Graphs
For researchers studying the complexity of graph burning, this work provides hardness results on regular graphs, a natural class, but the results are incremental as similar hardness was known for other classes.
The paper proves that the Burning Number Problem is NP-complete on connected cubic graphs and APX-hard on connected d-regular graphs for every fixed d ≥ 3, establishing computational hardness for this previously unexplored graph class.
The Burning Number Problem (BNP) models the spread of information or contagion in a network through a discrete-time process on a graph. At each step, one new vertex is selected as a burning source, while fire simultaneously spreads from previously burned vertices to their neighbors. The burning number of a graph is the minimum number of steps required to burn all vertices. The decision version asks whether the burning number is at most a given integer $k$. BNP is known to be NP-complete even on restricted graph classes such as path forests. We study BNP on connected regular graphs, a natural and previously unexplored graph class. We prove that BNP is NP-complete on connected cubic graphs, and moreover APX-hard under this restriction. We further show that BNP remains APX-hard on connected $d$-regular graphs for every fixed $d \geq 4$.