  Graph burning is a process of information spreading through the network by an
agent in discrete steps. The problem is to find an optimal sequence of nodes
which have to be given information so that the network is covered in least
number of steps. Graph burning problem is NP-Hard for which two approximation
algorithms and a few heuristics have been proposed in the literature. In this
work, we propose three heuristics, namely, Backbone Based Greedy Heuristic
(BBGH), Improved Cutting Corners Heuristic (ICCH) and Component Based Recursive
Heuristic (CBRH). These are mainly based on Eigenvector centrality measure.
BBGH finds a backbone of the network and picks vertex to be burned greedily
from the vertices of the backbone. ICCH is a shortest path based heuristic and
picks vertex to burn greedily from best central nodes. The burning number
problem on disconnected graphs is harder than on the connected graphs. For
example, burning number problem is easy on a path where as it is NP-Hard on
disjoint paths. In practice, large networks are generally disconnected and
moreover even if the input graph is connected, during the burning process the
graph among the unburned vertices may be disconnected. For disconnected graphs,
ordering of the components is crucial. Our CBRH works well on disconnected
graphs as it prioritizes the components. All the heuristics have been
implemented and tested on several bench-mark networks including large networks
of size more than $50$K nodes. The experimentation also includes comparison to
the approximation algorithms. The advantages of our algorithms are that they
are much simpler to implement and also several orders faster than the
heuristics proposed in the literature.
