Burning Two Worlds

Graph burning is a model for the spread of social influence in networks. The objective is to measure how quickly a fire (e.g., a piece of fake news) can be spread in a network. The burning process takes place in discrete rounds. In each round, a new fire breaks out at a selected vertex and burns it. Meanwhile, the old fires extend to their adjacent vertices and burn them. A burning schedule selects where the new fire breaks out in each round, and the burning problem asks for a schedule that burns all vertices in a minimum number of rounds, termed the burning number of the graph. The burning problem is known to be NP-hard even when the graph is a tree or a disjoint set of paths. For connected graphs, it has been conjectured [3] that burning takes at most \(\lceil \sqrt{n} \ \rceil \) rounds.

In this paper, we approach the algorithmic study of graph burning from two directions. First, we consider connected n-vertex graphs with minimum degree \(\delta \). We present an algorithm that burns any such graph in at most \(\sqrt{\frac{24n}{\delta +1}}\) rounds. In particular, for graphs with \(\delta \in \varTheta (n)\), all vertices are burned in a constant number of rounds. More interestingly, even when \(\delta \) is a constant that is independent of n, our algorithm answers the graph-burning conjecture in the affirmative by burning the graph in at most \(\lceil \sqrt{n} \rceil \) rounds. Then, we consider burning connected graphs with bounded pathlength or treelength. This includes many graph families, e.g., interval graphs (pathlength 1) and chordal graphs (treelength 1). We show that any connected graph with pathlength pl and diameter d can be burned in \(\lceil \sqrt{d-1} \rceil + pl\) rounds. Our algorithm ensures an approximation ratio of \(1+o(1)\) for graphs of bounded pathlength. We also give an algorithm that achieves an approximation ratio of \(2+o(1)\) for burning connected graphs of bounded treelength. Our approximation factors are better than the best known approximation factor of 3 for burning general graphs.