The Graph Burning Problem under Constrained Diffusion

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.