Graph Burning: Mathematical Formulations and Optimal Solutions

Jesús García-Díaz (), Lil María Xibai Rodríguez-Henríquez, Julio César Pérez-Sansalvador and Saúl Eduardo Pomares-Hernández
Additional contact information
Jesús García-Díaz: Consejo Nacional de Ciencia y Tecnología, Mexico City 03940, Mexico
Lil María Xibai Rodríguez-Henríquez: Consejo Nacional de Ciencia y Tecnología, Mexico City 03940, Mexico
Julio César Pérez-Sansalvador: Consejo Nacional de Ciencia y Tecnología, Mexico City 03940, Mexico
Saúl Eduardo Pomares-Hernández: Instituto Nacional de Astrofísica, Óptica y Electrónica, Coordinación de Ciencias Computacionales, Puebla 72840, Mexico

Mathematics, 2022, vol. 10, issue 15, 1-20

Abstract: The graph burning problem is an NP-hard combinatorial optimization problem that helps quantify how vulnerable a graph is to contagion. This paper introduces three mathematical formulations of the problem: an integer linear program (ILP) and two constraint satisfaction problems (CSP1 and CSP2). Thanks to off-the-shelf optimization software, these formulations can be solved optimally over arbitrary graphs; this is relevant because the only algorithms designed to date for this problem are approximation algorithms and heuristics, which do not guarantee to find optimal solutions. We empirically compared the proposed formulations using random graphs and off-the-shelf optimization software. The results show that CSP1 and CSP2 tend to reach optimal solutions in less time than the ILP. Therefore, we executed them over some benchmark graphs of order at most 5908. The previously best-known solutions for some of these graphs were improved. We draw some empirical observations from the experimental results. For instance, we find the tendency: the larger the graph’s optimal solution, the more difficult it is to find it. Finally, the resulting set of optimal solutions might be helpful as a benchmark dataset for the performance evaluation of non-exact algorithms.

Keywords: graph burning; integer programming; constraint satisfaction; social contagion (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/15/2777/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/15/2777/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:15:p:2777-:d:880888

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().