New heuristics for burning connected graphs

Document Type : Original Article

Authors

Department of Computer and Data Sciences, Shahid Beheshti University, Tehran, Iran

Abstract

The concept of graph burning and burning number $(bn(G))$ of a graph $G$ was introduced recently [4]. Graph burning models the spread of contagion (fire) in a graph in discrete time steps. $bn(G)$ is the minimum time needed to burn a graph $G$. The problem is NP-complete. In this paper, we develop first heuristics to solve the problem in general (connected) graphs. In order to test the performance of our algorithms, we applied them on some graph classes with known burning number such as $\theta$-graphs. We tested our algorithms on DIMACS and BHOSLIB that are known benchmarks for NP-hard problems in graph theory. We also improved the upper bound for burning number on general graphs in terms of their distance to cluster. Then we generated a data set of 1000 random graphs with known distance to cluster and tested our heuristics on them.

Keywords

Main Subjects

References

[1] S. Bessy, A. Bonato, J. Janssen, D. Rautenbach, and E. Roshanbin, Burning a graph is hard, Discrete Applied Mathematics, 232 (2017), pp. 73–87.
[2] E. Birmele, F. De Montgolfier, L. Planche, and L. Viennot ´ , Decomposing a graph into shortest paths with bounded eccentricity, (2017).
[3] A. Bonato, K. Gunderson, and A. Shaw, Burning the plane: densities of the infinite cartesian grid, arXiv preprint arXiv:1806.05642, (2018).
[4] A. Bonato, J. Janssen, and E. Roshanbin, Burning a graph as a model of social contagion, in International Workshop on Algorithms and Models for the Web-Graph, Springer, 2014, pp. 13–22.
[5] , How to burn a graph, Internet Mathematics, 12 (2016), pp. 85–100.
[6] A. Bonato and S. Kamali, Approximation algorithms for graph burning, in International Conference on Theory and Applications of Models of Computation, Springer, 2019, pp. 74–92.
[7] A. Bonato and T. Lidbetter, Bounds on the burning numbers of spiders and path-forests, Theoretical Computer Science, 794 (2019), pp. 12–19.
[8] R. Diestel, Graduate texts in mathematics, Graph theory, 173 (2000).
[9] D. Eichhorn, D. Mubayi, K. O’Bryant, and D. B. West, The edge-bandwidth of theta graphs, Journal of Graph Theory, 35 (2000), pp. 89–98.
[10] A. Hagberg, P. Swart, and D. S Chult, Exploring network structure, dynamics, and function using networkx, tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
[11] S. Kamali, A. Miller, and K. Zhang, Burning two worlds: algorithms for burning dense and tree-like graphs, arXiv preprint arXiv:1909.00530, (2019).
[12] , Burning two worlds, in International Conference on Current Trends in Theory and Practice of Informatics, Springer, 2020, pp. 113–124.
[13] A. S. Kare and I. V. Reddy, Parameterized algorithms for graph burning problem, in International Workshop on Combinatorial Algorithms, Springer, 2019, pp. 304–314.
[14] H. Liu, R. Zhang, and X. Hu, Burning number of theta graphs, Applied Mathematics and Computation, 361 (2019), pp. 246–257.
[15] D. Mitsche, P. Pra lat, and E. Roshanbin, Burning number of graph products, Theoretical Computer Science, 746 (2018), pp. 124–135.
[16] E. Roshanbin, Burning a graph as a model of social contagion, PhD thesis, Dalhousie University, 2016.
[17] R. A. Rossi and N. K. Ahmed, The network data repository with interactive graph analytics and visualization, in AAAI, 2015.
[18] K. A. Sim, T. S. Tan, and K. B. Wong, On the burning number of generalized petersen graphs, Bulletin of the Malaysian Mathematical Sciences Society, 41 (2018), pp. 1657–1670.
[19] M. Simon, L. Huraj, I. Dirgov ˇ a Lupt ´ akov ´ a, and J. Posp ´ ´ıchal, Heuristics for spreading alarm throughout a network, Applied Sciences, 9 (2019), p. 3269.
AUT Journal of Mathematics and Computing
Volume 3, Issue 2
September 2022
Pages 165-172

Files

Share

How to cite

Statistics