Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2022;52(2):1351-1361.
doi: 10.1007/s10489-021-02411-5. Epub 2021 May 20.

Faster heuristics for graph burning

Rahul Kumar Gautam  1 , Anjeneya Swami Kare  1 , Durga Bhavani S  1
Affiliations

Faster heuristics for graph burning

Rahul Kumar Gautam et al. Appl Intell (Dordr). 2022.

Abstract

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 that 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 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 50K 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.

Keywords: Burning number; Graph burning; Heuristic.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
An example graph, The vertex sequence [4,7,1] is an optimal burning sequence. The burning number of the graph is 3
Fig. 2
Fig. 2
An example disconnected graph. The burning number of the graph is 4
Fig. 3
Fig. 3
An example disconnected graph. The burning number of the graph is 3
Fig. 4
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
See this image and copyright information in PMC

References

    1. Bessy S, Bonato A, Janssen J, Rautenbach D, Roshanbin E. Bounds on the burning number. Discret Appl Math. 2018;235:16–22. doi: 10.1016/j.dam.2017.09.012. - DOI
    1. Bonato A (2020) A survey of graph burning
    1. Bonato A, Janssen J, Roshanbin E (2014) Burning a graph as a model of social contagion. In: Algorithms and models for the web graph, WAW 2014. Lecture Notes in Computer Science, vol 8882. Springer, pp 13–22
    1. Bonato A, Janssen J, Roshanbin E. How to burn a graph. Internet Math. 2016;12(1-2):85–100. doi: 10.1080/15427951.2015.1103339. - DOI
    1. Bonato A, Kamali S (2019) Approximation algorithms for graph burning. In: Theory and applications of models of computation. TAMC 2019. Lecture Notes in Computer Science. Springer, pp 74–92