k-Slow Burning: Complexity and Upper Bounds

The graph burning problem studies the speed at which information can spread in graphs across their edges. We discuss a recently introduced variant of the problem, k-slow burning, in which every burning vertex can only ignite up to k of its neighbours in each step of the burning process. We consider the complexity of computing the corresponding graph parameter, the k-slow burning number \(b_s(k,G)\) . We prove \(\mathcal{N}\mathcal{P}\) -hardness on multiple graph classes, most notably the class of graphs of radius 1, where normal graph burning is solvable in polynomial time. Furthermore, we show that among all connected graphs on n vertices, the burning number of the star graph, \(b_s(k,S_{n-1})\) , is maximal for \(k\in \{1,2\}\) and asymptotically maximal for fixed \(k\ge 3\) . This observation leads to a generalisation of the burning number conjecture in regard to k-slow burning.