Graph Burning: Bounds and Hardness

For an undirected graph $G$, graph burning is defined as follows: at step $t=0$ all vertices in $G$ are unburned. At each step $t\ge 1$, one new unburned vertex is selected to burn until we exhaust all the vertices. If a vertex is burned at step $t$, then all its unburned neighbors are burned in step $t+1$, and the process continues until there are no unburned vertices in $G$. The burning number of a graph $G$, denoted by $b(G)$, is the minimum number of steps required to burn all the vertices of $G$. The Burning Number problem asks whether the burning number of an input graph $G$ is at most $k$ or not. In this paper, we study the Burning Number problem both from an algorithmic and a structural point of view. The Burning Number problem is known to be NP-complete for trees with maximum degree at most three and interval graphs. Here, we prove that this problem is NP-complete even when restricted to connected cubic graphs and connected proper interval graphs. The well-known burning number conjecture asserts that all the vertices of a graph of order $n$ can be burned in $\lceil \sqrt{n}~\rceil$ steps. In line with this conjecture, upper and lower bounds of $b(G)$ are well-studied for various graph classes. Here, we provide an improved upper bound for the burning number of connected $P_k$-free graphs and show that the bound is tight up to an additive constant $1$. Finally, we study two variants of the problem, namely edge burning (only edges are burned) and total burning (both vertices and edges are burned). In particular, we establish their relationship with the burning number problem and evaluate the algorithmic complexity of these variants.