An application of information spread can be seen in public health campaigns. For instance in the case of covid pandemic, the health workers are struggling to get the information reach every house in order to spread awareness and prevent cornona virus spread. Take the scenario of one health-worker endeavour. She contacts a family in the village and explains the precautions to be taken up to protect oneself from the contagious infection and persuades that family to help spread awareness among their acquaintances. We assume that all the members who can be influenced by a family are covered in one step of the awareness campaign. In the burning number context, all those nodes that are covered are called as the 'burning' nodes. Next she has to approach another new family outside this circle of influence to spread the message. The whole process happens in discrete steps. Hence it is important to detect an optimal sequence of families to be approached by the health worker that would ensure coverage of the entire village for propagating the information in minimum time. In paper [12] , a similar application of passing information during emergency is discussed. Suppose a piece of information has to be sent to all the nodes in a network by a satellite. The satellite informs nodes (hubs) in discrete time steps. All the informed nodes communicate to their neighbours in parallel. Once a node is informed it is deemed to be in informed state. Process stops when all the nodes are informed.
Graphs are popular representations that model the social networks of the real world. Let G(V, E) be a graph where V is set of nodes depicting people, E denote relationship among the nodes. Initially all nodes are in unburned (uninformed) state. Given time steps t 0 , t 1 , t 2 · · · t b−1 , at t 0 one node is set to fire from outside. It starts burning and spreads the fire to its neighbours in a step wise fashion. During the process of burning, it is assumed that either the node is set on fire directly, called as source of fire, or node is burning by catching fire from a neighbour or it is not yet burnt. At i th time step, a new unburned node is set on fire from outside and all those nodes which have caught fire at t i−1 , burn their neighbours. The process stops when the entire graph is burning, that is, or all the nodes have received information. Thus the task is to find the minimum sequence of nodes that have to be chosen as sources of fire, that are directly burned from outside. It is desirable to spread the information through the network, or burn all the nodes of the network quickly. So the goal is to minimize the number of sources. The minimum number of steps needed to burn the entire graph or the length of the optimal burning sequence is called the burning number of the graph. The burning number of the graph G is denoted by bn(G). Let us consider graph in Fig. 1 . The vertex sequences [7, 4, 2, 1] , [4, 7, 1] and [3, 6, 8] are valid burning sequences, where as the sequence [7, 4, 1] is not a burning sequence. The burning number of the graph is 3, as the graph does not have burning sequence of length less than 3. [4, 7, 1] is an optimal burning sequence. The burning number of the graph is 3.
There are a few problems related to graph burning proposed in the literature. K-centre problem [10] , is one in which the K centres are chosen simultaneously as sources of fire. As a result the nodes burn in parallel and hence very quickly. The K-centres problem is also NP-hard. The Firefighter problem [9] is a comple-mentary version of the graph burning problem, in which a firefighter protects a node to reduce spread of fire in the graph. At each time step, the firefighter selects a node through which he can protect maximum number of nodes. On the other hand, in graph burning, a node is selected in such a way that it can burn a maximum number of nodes. Therefore the firefighter defends and in graph burning the source of fire burns. Active influence spreading in social networks [6, 7, 15] is the problem of selection of seed sets that can influence as many nodes as possible. In this paper, we propose three heuristics for the Graph Burning problem. The proposed heuristics are tested on some real world data sets and their performance is compared to the existing heuristics.
Bonato et al. [2] introduced the Graph Burning problem and the parameter burning number. They have studied the properties of Graph Burning and proposed bounds for burning number. Bessy et al. [24] proved that the decision version of the Graph Burning problem is NP-Complete. There has been lot of attention paid towards studying the Graph Burning problem from theoretical point of view. The complexity and the algorithms for the Graph Burning problem for special graph classes was studied in [3, 11, 21, 23, 24] . The characterization and bounds for burning number was studied in [1, 2, 3, 5, 13, 17, 19, 20] . Approximation algorithms for the burning number problem was studied in [4, 5, 13, 24] . Parameterized complexity of the Graph Burning problem was studied in [14, 16] .
Šimon et al. [12] proposed heuristics for the Graph Burning problem. They have studied the Graph Burning problem empirically using both real world data sets as well as synthetic data sets. They proposed three heuristics based on Eigenvector centrality, namely Maximum Eigenvector Centrality Heuristic (MECH), Cutting Corners Heuristic (CCH) and Greedy Algorithm with Forward-Looking Search Strategy Heuristic (GFSSH). The MECH is a greedy heuristic, at each iteration it selects a (central) node with maximum eigenvector centrality. In CCH, at each iteration, first it finds a set of corner nodes of the graph, using these corner nodes, a set of central nodes are selected based on eigenvector centrality. Among these central nodes a best central node is selected using weighted aggregated sum product assessment (WASPAS) algorithm. In GFSSH a set of 20 central nodes are generated and at each iteration a best central node is selected by combining greedy heuristic and forward looking search.
Šimon et al. [12] also implemented the 3-approximation algorithm (3-APRX) of Bonato et al. [4] to compare the performance of their heuristics. They have tested the heuristics on some synthetic tree data sets also, however they did not implement the 2-approximation algorithm (2-APRX) for trees of Bonato et al. [4] . As stated in [4] , the 2-approximation algorithm can also be used to compute an upper bound on burning number of any graph. If G is the original graph and T be any spanning tree of G then bn(G) ≤ bn(T ). So the 2-approximation algorithm for trees can also be used to compute an upper bound on the burn-ing number of the graph. However the computed upper bound need not be a 2-approximation of the original graph.
Recently, Farokh et al. [8] proposed six heuristics for the Graph Burning problem. Their heuristics are not based on Eigenvector centrality. They call the vertices in the burning sequence as activators. The first four heuristics are based on different strategies to obtain the first activator and the rest of the activators. First activator is either a central node or it is selected randomly. The rest of the activators are selected such that each vertex has a unique activator. In other words reduce overlapping among the circle around the activators. The other two heuristics are based on diameter, DFS and BFS of the graph.
We propose three heuristics for the Graph Burning problem. The heuristics are based on eigenvector centrality. We propose the following heuristics: Backbone Based Greedy Heuristic (BBGH), Improved Cutting Corners Heuristic (ICCH) and Component Based Recursive Heuristic (CBRH). We have also implemented both 3-approximation and 2-approximation algorithms of Bonato et al. [4] . We compare our implemented heuristics with GFSSH, the best performing heuristic of Šimon et al. [12] . We also compare performance of our algorithms with the results of Farokh et al. [8] .
Note that both [12] and [8] tested their heuristics on smaller data sets. We test our heuristics on bigger data sets as well. For example, some of the data sets we used are DIMACS, BOSHLIB, Facebook blue verified pages friends network, DBLP-citation network and huge graphs with size more than 50, 000 nodes like Gemsec-Deezer(HR) (music friendship network in Europe). All three heuristics are performing equally well on all the data sets. Our heuristics are faster than the GFSSH of Šimon et al. [12] and efficient compared to heuristics of Farokh et al. [8] . Moreover our heuristics are easy to implement.
The rest of the paper is organized as follows: In Section 3, we discuss greedy heuristics. The Backbone Based Greedy Heuristic (BBGH) is discussed in Section 3.1. The Improved Cutting Corners Heuristic (ICCH) is discussed in Section 3.2. In Section 3.3, we discuss the Component Based Recursive Heuristic (CBRH). In Section 4, we discuss our results and some observations. We give conclusions In Section 5.
We consider the following decision version of the Graph Burning, which asks to check if the graph G can be burned in at most b time steps. If we have an algorithm for Burn-Graph(G, b), we can use binary search to compute minimum b for which the Burn-Graph(G, b) returns true. As the Graph Burning is NPhard, we can not expect to have a exact polynomial time algorithm for Burn-Graph(G, b). In this paper, we propose heuristics for Burn-Graph(G, b). The heuristics for Burn-Graph(G, b), if it returns true, it means that the algorithm is successful in finding a burning sequence of length at most b. If it returns f alse, it means that the algorithm failed to find a burning sequence of length at most b. Note that, in the later case, the graph can still be burned in at most b steps.
Burn-Graph(G, b): Input: A graph G = (V, E) and a positive integer b. Question: Does the graph have a burning sequence of length at most b?
We propose three heuristics for Burn-Graph(G, b). First two are greedy in nature and the third one is a component based recursive algorithm. First we discuss the greedy algorithms and then the recursive algorithm.
At the outset, the process underlying the greedy algorithms is as shown in Algorithm 1. At each iteration, the function getBestCentralN ode() extracts an unburned vertex to burn next. The two heuristics differ in the procedure getBestCentralN ode().
Input : G = (V, E) and a positive integer b Output: Returns true if algorithm finds a burning sequence of length at most b or false otherwise
for k ← 0 to j do 
We call a longest path starting at a node with minimum centrality value and containing nodes with high centrality values as the backbone path. A node on the backbone path can potentially burn more vertices. With this intuition we propose the Backbone Based Greedy Heuristic (BBGH). We extract the backbone path and for each vertex in the backbone path, we see how many vertices the vertex can burn, if we burn the vertex in the current time step. The vertex which leads to maximum number of burned vertices is chosen as the best central node. Here the crucial step is: how to extract the backbone path?. A backbone path is a longest path starting at a node with minimum centrality and containing nodes with high centrality values. To compute backbone path we use BFS traversal. We compute BFS tree rooted at a node with minimum centrality value. In this rooted tree we look at the nodes at highest depth, there can be more than one such node. For all these nodes we consider shortest path from the root to the node and compute average centrality of all the nodes in the path. A path with maximum average centrality is considered as the backbone path. The procedure getBackboneP ath() returns a path.
Let us take backbone path as an array bbP ath. For each vertex v ∈ bbP ath in decreasing order of centrality values, compute
, set of all the vertices which are at a distance at most r from v. Then whichever node gives maximum |S| value, will become the best central node. If the graph is disconnected, then backbone path of each component is extracted and which ever vertex of these backbone paths gives maximum |S| value, we return that vertex as the best central node. The complete algorithm is shown in Algorithm 2. Working of the BBGH is shown in Table 1 with an example. Note that, for the graph given in Table 1 . Trace of BBGH, the Algorithms 1 and 2. For each iteration vertices shown in red color are not part of the graph G. The estimated burning number of the graph is 4. Table 1 , GFSSH of Šimon et al. [12] gives a burning sequence of size 5, where as our BBGH burns the graph in 4 time steps.
Šimon et al. [12] , presented heuristic called Cutting Corner Heuristic (CCH). Their algorithm has O(mn) time complexity. We present a similar heuristic which also runs in worst case O(mn) time. However our algorithm is easy to implement and runs faster in practice as we avoid computation of average path length and call to weighted aggregated sum product assessment (WASPAS) method.
Let r be the number of time steps available to burn the graph. We start by computing the centrality values. Let u be the node with maximum centrality. We remove the r neighborhood of u, that is, all the vertices in the set N r G [u] from the graph G. If the resulting graph is empty, then we return the vertex u as the best central node. Otherwise, let the resulting graph have q components, say C[0], C [1] , · · · , C[q − 1]. For each component C[i], 0 ≤ i < q, we take the minimum centrality vertex (say v i ) of the component C[i] and compute shortest path from u to v i and let the shortest path be denoted by P [i]. We visualize P [0], P [1], · · · , P [q − 1] as a matrix (multi-list), where each P [i] is treated as a row in the matrix. Now for each column of the matrix, we pick r nodes in decreasing order of degree. If c is the number of columns of the matrix, we will get at most r * c such nodes. For each of these nodes, we compute S = N r G [.] value. Then whichever node gives maximum |S| value, will become the best central node. The process is depicted in the Algorithm 3. Working of the ICCH is shown in Table 2 with an example. From our results, we observe that our ICCH performs better than the CCH of Šimon et al. [12] .
Input : G = (V, E) and a non-negative integer r Output: Returns Best central node 1 getBestCentralNode(G,r) begin 
If the graph is disconnected, choosing of a component to burn a vertex can make a difference. Let us consider the graphs in Fig. 2 and Fig. 3 . These graphs have two components. Let us see the following criterion to select the component to burn a vertex.
1. Component with maximum size: If we choose component with maximum number of vertices, we need a burning sequence of length 4 to burn the graph in Fig. 2 and we need a burning sequence of length 4 to burn the graph in Fig. 3 . But the actual burning number of the graph in Fig. 3 is 3. 2. Component with maximum path length: If we choose component with maximum path length, we need a burning sequence of length 5 to burn the graph in Fig. 2 and we need a burning sequence of length 3 to burn the graph in Fig. 3 . But the actual burning number of the graph in Fig. 2 is 4 . Table 2 . Trace of ICCH, the Algorithms 1 and 3. For each iteration vertices shown in red color are not part of the graph G. The estimated burning number of the graph is 5.
Original Graph (G) For the graph given in Fig. 2 , the Backbone Based Greedy Heuristic will choose the component with vertex set {1, 2, 3 · · · , 9} and vertex 5 is chosen as the best central node. Now we can see that we require 5 time steps to burn the graph. But the burning number of the graph is 4. The optimum burning sequence chooses a vertex 20 from the second component. Note that even if graph is connected in the beginning, in the subsequent iterations the graph can be disconnected and this situation can arise. Therefore choosing a component is very crucial. Therefore the question is what is the criteria to select the best component of the graph. Ideally we should choose a component that has maximum burning number. Table 1 , the trace of the algorithm is very similar that of Algorithm 2.
Our BBGH and ICCH fails to compute optimal burning sequence of either graph in Fig. 2 or Fig. 3 . But our CBRH computes optimal burning sequence for both the graphs. For the connected graph given in Fig. 4 , our CBRH computes the optimal burning number but our other two heuristics, BBGH, ICCH and GFSSH of Šimon et al. [12] fail to compute optimal burning sequence. This concludes the significance of our ICCH. Fig. 4 . An example graph, The vertex sequence [13, 21, 3, 7, 6] is an optimal burning sequence. The burning number of the graph is 5.
Input : G = (V, E), a positive integer b and a dictionary D Output: Returns the length of minimal burning sequence of size at most b or -1 if algorithm fails to find burning sequence of length at most b. Note that the algorithm prints the burning sequence as well.
⊲ An array to represent burning sequence 
We tested our heuristics on the following data sets:
1. The Network Data Repository [22] -Netscience -Polblogs -Reed98 -Mahindas -Cite-DBLP 2. Stanford large network dataset collection (SNAP Datasets) [18] -
We also generated 100 random trees and tested the performance of the algorithms. All the heuristics are implemented in Python programming language. The algorithms have been implemented on a system with processor Intel Core i5, processor speed of 2.7 GHz having dual core and 8GB RAM. We compare performance of our heuristics with those of [12] and [8] . The Table 3 shows the estimated values of the burning number for various algorithms. We have compared our results with 3-approximation and 2-approximation algorithms of Bonato et al. [4] , GFSSH, the best performing heuristic of [12] 1 . We have also listed the number of recursive calls made by our Component Based Recursive Heuristic. It can be observed that, at the outset the algorithm looks like an exponential algorithm, but in practice the number of recursive calls made is very less even for bigger graphs. Note that for all the social networking data sets and other data sets that have been considered in this paper, the diameter (radius) of the graph is very small. The burning number of a graph with radius r is at most r + 1. As the radius of the graphs is very small, improving the burning by even a small number is tough. From Table 3 we observe that our heuristics are competitive to the best heuristic of Šimon et. al. [12] . Table 4 shows the running time comparison of our heuristics with that of GFSSH, the best performing heuristic of [12] . Our heuristics are faster than that of [12] . Note that both Šimon et. al. [12] and Farokh et al. [8] tested their heuristics on smaller data sets. As our heuristics are faster, they take lesser time on even bigger data sets.
While comparing with heuristics of Farokh et al. [8] , it can be seen that our heuristics give better results for some of the graphs. The Table 5 shows the comparison of performance of our heuristics with that of [8] . Table 3 . Comparison of estimated burning number of approximation algorithms [4] , GFSSH of [12] and our heuristics. The last column shows the number of recursive calls made by CBRH. *-For Netscience and Mahindas data sets, [12] quoted burning number as 6, however when we run their program on our machine we got 7 and 5 respectively. Barabasi 
In this paper, we proposed three heuristics for Graph Burning problem, namely, Backbone Based Greedy Heuristic (BBGH), Improved Cutting Corners Heuristic (ICCH) and Component Based Recursive Heuristic (CBRH). Firstly, we show a need for each heuristic by constructing the required example graphs. That is, we show a graph for which BBGH finds a better burning number compared to GFSSH; a graph on which ICCH finds a better burning number than BBGH and