2022/04/02 by Gautam, Rahul Kumar, Kare, Anjeneya Swami, S, Durga Bhavani
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2204.00772
Given a graph G=(V,E), the problem of \gb is to find a sequence of nodes from V, called burning sequence, in order to burn the whole graph. This is a discrete-step process, in each step an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A node that is burnt spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The \gb problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a 3-approximation algorithm for general graphs and a 2- approximation algorithm for trees. In this paper, we propose an approximation algorithm for trees that produces a burning sequence of length at most \lfloor 1.75b(T) \rfloor + 1, where b(T) is length of the optimal burning sequence, also called the burning number of the tree T. In other words, we achieve an approximation factor of (\lfloor 1.75b(T) \rfloor + 1)/b(T).