Graph Burning
Edit
This entry is adapted from the peer-reviewed paper 10.3390/math10152777

The graph burning problem is a relatively new combinatorial optimization problem that helps quantify a graph's vulnerability. It is defined in terms of a fundamental diffusion model.

graph burning social contagion

1. Introduction

The graph burning problem (GBP) is an NP-hard combinatorial optimization problem introduced in 2014 in the context of social contagion [1]. This problem, concerned with the sequential spread of information over a graph, considers that information can be spread from different places and times [1][2]. In this entry, by graph we refer to an undirected simple graph [3]. Computer network message propagation is an example of a real-world problem that the GBP may model; in this scenario, an initial spreading entity can send a message one host at a time, while these hosts can propagate the message only to their neighbors [4][5]. The GBP may model other real-world problems: social contagion in social networks and the spread of viral infections under a very idealistic context [6].
The GBP receives a graph G=(V,E) as input, and its goal is to find a minimum length sequence of vertices (𝑠1,𝑠2,…,𝑠k) that burns all graph’s vertices by following the burning process. This process consists of repeating the following steps from 𝑖=1 to k, where all vertices are unburned at the beginning, and once a vertex is burned, it remains in that state.

    a) The neighbors of the burned vertices get burned.

    b) Vertex 𝑠i gets burned.

Figure 1 shows a simple example of the burning process. The length of an optimal burning sequence for a given graph G is denoted by b(G) and is known as the burning number.

Figure 1. An optimal burning sequence for a nine vertices path is (𝑣3,𝑣7,𝑣9). The burning process of this sequence is depicted by each 𝑖 ∈ {1,2,3} with its corresponding steps a and b. Notice that vertex 𝑣3 burns all vertices at distance at most 2, vertex 𝑣7 burns all vertices at distance at most 1, and vertex 𝑣9 only burns itself.

Since the above example is too simple, Figures 2-4 show the optimal burning sequence of some classical graph instances from the literature.

Figure 2. An optimal burning sequence of Zachary's karate club graph.

Figure 3. An optimal burning sequence of a 33x33 2D lattice.

Figure 4. An optimal burning sequence of a 10x10x10 3D lattice.

2. Graph Burning: Properties, Models, and Algorithms

The decision version of the GBP is NP-complete. This problem receives as input a graph 𝐺=(𝑉,𝐸) and a positive integer k; it asks if a burning sequence of length at most k exists. The problem remains NP-complete when restricted to trees of maximum degree three, chordal graphs, bipartite graphs, planar graphs, spider graphs, and disconnected graphs [2]. The optimization version of the problem also remains NP-hard for trees and graphs with disjoint paths [7]. Regarding arbitrary graphs, two approximation algorithms are reported in the literature; they have an approximation factor of 3 and 3−2/𝑏(𝐺), respectively [7][8]. There is a 2-approximation algorithm for trees, a 1.5-approximation algorithm for graphs with disjoint paths, and a 2-approximation algorithm for square grids [6][7]. For minimization problems, a 𝜌-approximation algorithm returns solutions of size at most 𝜌·𝑂𝑃𝑇, where 𝑂𝑃𝑇 is the size of the optimal solution and 𝜌≥1. In the case of maximization problems, a 𝜌-approximation algorithm returns solutions of size at least (1/𝜌)·𝑂𝑃𝑇 [9]. Besides approximation algorithms, some heuristics have been proposed too [4][5]; these are mainly based on centrality measures and binary search over the set of possible values of 𝑏(𝐺). The GBP has been formulated using integer linear programming and constraint satisfaction problems. Using these formulations and off-the-shelf optimization software, graphs with up to 5908 vertices have been solved to proven optimality [10].
The GBP has been approached mostly from a theoretical point of view. As a result, many of its properties over specific graph families have been identified. Among these families are paths [2][7], trees [2][7], grids [6], intervals [6], fences [11], theta [12], spiders [13], path-forests [2][7][13], caterpillars [14], products [15], and generalized Petersen graphs [16]. Some of the main properties of the GBP are the following. All paths and cycles G of order n have 𝑏(𝐺)=⌈𝑛1/2⌉, all graphs G with a Hamiltonian path have 𝑏(𝐺)≤⌈𝑛1/2⌉ [1][2], all spiders and caterpillars G have 𝑏(𝐺)≤⌈𝑛1/2⌉ [13][14], all complete graphs G of order at least two have 𝑏(𝐺)=2, and all perfect binary trees G of depth r have 𝑏(𝐺)=𝑟+1. Based on these properties, a conjecture on the upper bound of the burning number of connected graphs was formulated by Bonato et al. [1]: Every connected graph G of order n has burning number b(G)≤⌈𝑛1/2⌉. This conjecture, known as the burning number conjecture, is one of the most important open questions in the area. To date, the best-known bound for the burning number of arbitrary connected graphs is 𝑏(𝐺)≤⌈(4·𝑛/3)1/2⌉+1 [17].
The GBP resembles other NP-hard problems, such as the vertex k-center problem (VKCP) and the firefighter problem (FP). The VKCP consists of finding the best location for a set of 𝑘 ∈ ℤ centers, where such locations are the ones that minimize the maximum distance a customer has to travel to its nearest center [18][19][20]. Although the VKCP and the GBP are different, their approximation algorithms are conceptually similar [7][8][20]. This similarity comes from the fact that the VKCP has a polynomial-time reduction to the minimum dominating set problem, which can be viewed as the problem of burning all vertices in parallel in one single step [20][21][22][23]. Regarding the FP, it aims at protecting vertices from burning given an initial set of fire sources [24][25][26]. Although GBP and FP have different goals, the latter’s integer linear program (ILP) served as inspiration to define an integer linear program for the GBP [10].

References

  1. Bonato, A.; Janssen, J.; Roshanbin, E. Burning a graph as a model of social contagion. In International Workshop on Algorithms and Models for the Web-Graph; Springer: Berlin/Heidelberg, Germany, 2014; pp. 13–22.
  2. Bessy, S.; Bonato, A.; Janssen, J.; Rautenbach, D.; Roshanbin, E. Burning a graph is hard. Discret. Appl. Math. 2017, 232, 73-87.
  3. Diestel, R.. Graph Theory; Springer Graduate Texts in Mathematics: Springer: Berlin/Heidelberg, Germany, 2017; pp. 2.
  4. Šimon, M.; Huraj, L.; Luptáková, I.D.; Pospíchal, J. Heuristics for spreading alarm throughout a network. Appl. Sci. 2019, 9, 3269.
  5. Gautam, R.H.; Kare, A.S.; Surampudi, D.B. Faster heuristics for graph burning. Appl. Intell. 2021, 52, 1351–1361.
  6. Gupta, A.T.; Lokhande, S.A.; Mondal, K. Burning grids and intervals. In Proceedings of the Algorithms and Discrete Applied Mathematics, Rupnagar, India, 11–13 February 2021; pp. 66–79
  7. Bonato, A.; Kamali, S. Approximation algorithms for graph burning. In Proceedings of the International Conference on Theory and Applications of Models of Computation, Kitakyushu, Japan, 13–16 April 2019; pp. 74–92.
  8. García-Díaz, J.; Pérez-Sansalvador, J.C.; Rodríguez-Henríquez, L.M.X.; Cornejo-Acosta, J.A. Burning Graphs Through Farthest-First Traversal. IEEE Access 2022, 10, 30395–30404.
  9. Vazirani, V.V.. Approximation Algorithms; Springer Science & Business Media: Berlin/Heidelberg, Germany, 2013; pp. 1.
  10. García-Díaz, J.; Rodríguez-Henríquez, L.M.X.; Pérez-Sansalvador, J.C.; Pomares-Hernández, S.E. Graph Burning: Mathematical Formulations and Optimal Solutions. Mathematics 2022, 10, 2777.
  11. Bonato, A.; English, S.; Kay, B.; Moghbel, D. Improved bounds for burning fence graphs. Graphs Comb. 2021, 37, 2761–2773.
  12. Liu, H.; Zhang, R.; Hu, X. Burning number of theta graphs. Appl. Math. Comput. 2019, 361, 246–257.
  13. Bonato, A.; Lidbetter, T. Bounds on the burning numbers of spiders and path-forests. Theor. Comput. Sci. 2019, 794, 12-19.
  14. Liu, H.; Hu, X.; Hu, X. Burning number of caterpillars. Discret. Appl. Math. 2020, 284, 332–340.
  15. Mitsche, D.; Prałat, P.; Roshanbin, E. Burning number of graph products. Theor. Comput. Sci. 2018, 746, 124–135.
  16. Sim, K.A.; Tan, T.S.; Wong, K.B. On the burning number of generalized petersen graphs. Bull. Malaysian Math. Sci. 2018, 41, 1657–1670.
  17. Bastide, P.; Bonamy, M.; Bonato, A.; Charbit, P.; Kamali, S.; Pierron, T.; Rabie, M. Improved Pyrotechnics: Closer to the Burning Number Conjecture. Preprint. 2022. Available online: https://arxiv.org/abs/2110.10530 (accessed on 31 July 2022).
  18. Gonzalez, T.F. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 1985, 38, 293–306.
  19. Hochbaum, D.S.; Shmoys, D.B. A best possible heuristic for the k-center problem. Math. Oper. Res. 1985, 10, 180–184.
  20. Garcia-Diaz, J.; Menchaca-Mendez, R.; Menchaca-Mendez, R.; Hernández, S.P.; Pérez-Sansalvador, J.C.; Lakouari, N. Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation. IEEE Access 2019, 7, 109228–109245.
  21. Cornejo Acosta, J.A.; García Díaz, J.; Menchaca-Méndez, R.; Menchaca-Méndez, R. Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem. Mathematics 2020, 8, 1551.
  22. Grandoni, F. A note on the complexity of minimum dominating set. J. Discret. Algorithms 2006, 4, 209–214.
  23. Hernández-Gómez, J.C.; Reyna-Hérnandez, G.; Romero-Valencia, J.; Rosario Cayetano, O. Transitivity on Minimum Dominating Sets of Paths and Cycles. Symmetry 2020, 12, 2053.
  24. Hartnell, B. Firefighter! An application of domination. Presentation. In Proceedings of the 25th Manitoba Conference on Combinatorial Mathematics and Computing, Winnipeg, MB, Canada, 29 September–1 October 1995.
  25. Develin, M.; Hartke, S.G. Fire containment in grids of dimension three and higher. Discrete Appl. Math. 2007, 155, 2257–2268.
  26. García-Martínez, C.; Blum, C.; Rodriguez, F.J.; Lozano, M. The firefighter problem: Empirical results on random graphs. Comput. Oper. Res. 2015, 60, 55–66.
More
Related Content
Application of Machine Learning Models in Social Sciences: Managing Nonlinear Relationships Entry
The increasing complexity of social science data and phenomena necessitates using advanced analytical techniques to capture nonlinear relationships that traditional linear models often overlook. This chapter explores the application of machine learning (ML) models in social science research, focusing on their ability to manage nonlinear interactions in multidimensional datasets. Nonlinear relationships are central to understanding social behaviors, socioeconomic factors, and psychological processes. Machine learning models, including decision trees, neural networks, random forests, and support vector machines, provide a flexible framework for capturing these intricate patterns. The chapter begins by examining the limitations of linear models and introduces essential machine learning techniques suited for nonlinear modeling. A discussion follows on how these models automatically detect interactions and threshold effects, offering superior predictive power and robustness against noise compared to traditional methods. The chapter also covers the practical challenges of model evaluation, validation, and handling imbalanced data, emphasizing cross-validation and performance metrics tailored to the nuances of social science datasets. Practical recommendations are offered to researchers, highlighting the balance between predictive accuracy and model interpretability, ethical considerations, and best practices for communicating results to diverse stakeholders. This chapter demonstrates that while machine learning models provide robust solutions for modeling nonlinear relationships, their successful application in social sciences requires careful attention to data quality, model selection, validation, and ethical considerations. Machine learning holds transformative potential for understanding complex social phenomena and informing data-driven psychology, sociology, and political science policy-making.
Keywords: machine learning in social sciences; nonlinear relationships; model interpretability; predictive analytics; imbalanced data handling
Assembly Theory Entry
Assembly theory is a framework for quantifying selection, evolution, and complexity. It, therefore, spans various scientific disciplines, including physics, chemistry, biology, and information theory. Assembly theory is rooted in the assembly of an object from a set of basic building units, forming an initial assembly pool and from subunits that entered the assembly pool in previous assembly steps. Hence, the object is defined not as a set of point particles but by the history of its assembly, where the assembly index is the smallest number of steps required to assemble the object.
Keywords: assembly theory; complexity; origin of life; emergent dimensionality; mathematical physics
Coverage2 Image
a graph represent the single cell coverage. Source: http://openi.nlm.nih.gov/detailedresult.php?img=3549815_1471-2164-14-S1-S7-1&req=4.
Keywords: bacteria; Escherichia coli (E. coli)
Economic Sociology Entry
Economic sociology is a subfield of sociology that examines the social foundations of economic behavior, institutions, and systems. Unlike mainstream economics, which primarily relies on mathematical models and rational-choice theories, economic sociology explores how social structures, cultural norms, power relations, and historical contexts shape economic life. This field integrates insights from classical sociology (Karl Marx, Max Weber, Émile Durkheim) and has evolved to include contemporary debates on markets, globalization, capitalism, economic networks, and financial crises. Economic sociology is concerned with topics such as labor markets, economic inequality, social capital, consumer behavior, and the role of institutions in economic development.
Keywords: Economic Sociology; Cultural Economy; Labor and Work; Class and Economic Inequality
Sir Timothy Berners-Lee: Why He Chose to Give Away His Billion-Dollar Invention Video
Did you know? Sir Timothy Berners-Lee, the creator of the World Wide Web, could have profited from his billion-dollar invention but chose to make it a public resource for everyone. In the late 1980s, while working at European Organization for Nuclear Research, Tim saw that scientists needed a faster way to share data globally. He invented HTML, HTTP, and URLs—three technologies that became the foundation of the modern internet. However, Tim didn’t patent his creations. Economists believe he may have missed out on a fortune by not doing so. With global internet industries earning trillions annually, he could have earned billions in patent fees. Why? Because his goal wasn’t just to make money—it was to shape a future that would benefit everyone. Next time you browse the web, remember: Tim’s decision to make his invention free didn’t just change the internet—it changed the world.
Keywords: Sir Timothy Berners-Lee; World Wide Web; internet
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Graph Burning
Information
Subjects: Computer Science, Theory & Methods
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Jesús García Díaz
View Times: 655
Revisions: 7 times (View History)
Update Date: 21 Jul 2023
Table of Contents
Video Production Service
Feedback