The Graph Burning Problem under Constrained Diffusion

Enrico Iurlano (), Günther R. Raidl () and Marko Djukanović ()
Additional contact information
Enrico Iurlano: TU Wien, Algorithms and Complexity Group
Günther R. Raidl: TU Wien, Algorithms and Complexity Group
Marko Djukanović: University of Banja Luka, Faculty of Natural Sciences and Mathematics

A chapter in Advances in Optimization and Wildfire, 2026, pp 139-154 from Springer

Abstract: Abstract Relying on a simplified model of fire spread, the Graph Burning Problem is an NP-hard combinatorial optimization problem that yields a metric of social contagion or vulnerability of a network. It concerns a discrete-time process on a simple undirected graph, with, in each timestep, a diffusion phase of fire towards all neighbors of “burned” vertices and a second phase, in which a next not-yet-burned vertex is ignited by an external actor. The aim is to find the minimum number of timesteps together with suitable choices of vertices for the actor such that the whole set of vertices gets burned. The applicability of the problem becomes more relevant when one takes into account that diffusion might realistically be suppressed by given natural obstacles and limitations as well as implemented countermeasures. Therefore, this paper proposes the Constrained Diffusion Graph Burning Problem, where vertex-specific thresholds are considered that determine the maximum number of neighbors the vertex can ignite. We consider the aspect of expiration, i.e., burned vertices are permitted to diffuse fire only immediately after becoming burned, but not to a later timestep. These assumptions not only appear meaningful in the context of fire spread but also within dynamics of viral contagion and rapid information dissemination. A time-indexed (mixed) integer linear programming approach is proposed in two versions: The first version one-hot encodes the time, and the second one handles the time using a Miller-Tucker-Zemlin formulation. Finally, a greedy heuristic is proposed and compared to the previous formulations.

Keywords: Social contagion model; Fire spread simulation; Mixed integer linear programming (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:lnopch:978-3-032-03108-2_9

Ordering information: This item can be ordered from
http://www.springer.com/9783032031082

DOI: 10.1007/978-3-032-03108-2_9

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().