Approximation Algorithms for the Graph Burning on Cactus and Directed Trees

07/17/2023
by   Rahul Kumar Gautam, et al.
0

Given a graph G=(V, E), the problem of Graph Burning is to find a sequence of nodes from V, called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning 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. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose 1) A 2.75-approximation algorithm for a cactus graph (undirected), 2) A 3-approximation algorithm for multi-rooted directed trees (polytree) and 3) A 1.905-approximation algorithm for single-rooted directed tree (arborescence). We implement all the three approximation algorithms and the results are shown for randomly generated cactus graphs and directed trees.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset