Burning and w-burning of geometric graphs.

Graph burning runs on discrete time-steps. The aim is to burn all the vertices in a given graph using a minimum number of time-steps. This number is known to be the burning number of the graph. The spread of social influence, an alarm, or a social contagion can be modeled using graph burning. The less the burning number, the faster the spread.It is well-known that the optimal burning of general graphs is NP-complete. Further, graph burning has been shown to be NP-complete on a vast majority classes of graphs. Approximation results also exist for several graph classes. In this article, we show that the burning problem is NP-complete on connected interval graphs and permutation graphs. We also study the burning properties of grids. More precisely, we show that the lower bound of the burning number of a grid (l x b) is at least (l x b)31. We provide a 2-approximation for burning a square grid. We extend the study of the w-burning problem, a variation of the graph burning problem where we allow a constant w number of vertices to be burnt in any time-step.We prove that w-burning of interval, spider, and permutation graphs are NP-complete for any constant w. We also provide a 2-approximation for the w-burning problem on trees.(c) 2023 Elsevier B.V. All rights reserved.