Burning Path-Like and Clique-Like Graphs
摘要
Graph Burning is a model that captures the spread of information in a network. Here, in each round, the fire starts at an unburned vertex called fire source, and in every subsequent round, fire spreads from every burned vertex to all of its unburned neighbors. Given a graph \(G=(V,E)\) and an integer b, the Graph Burning problem asks whether all vertices of G can be burned in b rounds. The optimization version of the Graph Burning problem asks to find the minimum b, such that G can be burned in b rounds. The Graph Burning problem is known to be NP-complete even for disjoint paths. Further, it is known that the Graph Burning problem is W[1]-hard when parameterised by b and the optimization version of the Graph Burning problem is known to be APX-hard. In this paper, we give a PTAS for the Graph Burning problem, for a specific graph class and also study the parameterised complexity of the problem under many parameterisations.