Fighting Fires on Random Threshold Graphs

Rose Winter, St. Catherine University

Abstract

In order to develop a method for stopping the spread of some phenomenon over a network, we studied the probability distribution of the firefighter game played on a random threshold graph. The firefighter game models the spread of some condition (fire) within a system represented by a graph. The objective is, through an optimal placement of a limited supply of resources (firefighters), to keep the largest possible number of vertices from burning; we refer to the vertices that are never burned as saved. We analyzed firefighter on random threshold graphs formed by randomly assigning each vertex a weight between 0 and 1, so that an edge connects a pair of vertices if and only if the sum of their weights is greater than 1. We developed and proved an optimal strategy for playing the firefighter game on threshold graphs, and with the strategy constructed simulations, both by hand and with computer programs. By examining the patterns in the simulations, we conjectured our results. We found and proved the probability distribution for the number of vertices saved on a random threshold graph, the distribution depending on relationships between the number of vertices in the graph, the number of firefighters placed per turn, and the number of edges attached to the vertex at which the fire began. These results could be generalized so as to assist in determining where vaccinations would be best delivered so as to stop a pandemic, which waterways are most critical in monitoring for invasive species, and other situations where a harmful substance is spreading through a network.

 

Fighting Fires on Random Threshold Graphs

In order to develop a method for stopping the spread of some phenomenon over a network, we studied the probability distribution of the firefighter game played on a random threshold graph. The firefighter game models the spread of some condition (fire) within a system represented by a graph. The objective is, through an optimal placement of a limited supply of resources (firefighters), to keep the largest possible number of vertices from burning; we refer to the vertices that are never burned as saved. We analyzed firefighter on random threshold graphs formed by randomly assigning each vertex a weight between 0 and 1, so that an edge connects a pair of vertices if and only if the sum of their weights is greater than 1. We developed and proved an optimal strategy for playing the firefighter game on threshold graphs, and with the strategy constructed simulations, both by hand and with computer programs. By examining the patterns in the simulations, we conjectured our results. We found and proved the probability distribution for the number of vertices saved on a random threshold graph, the distribution depending on relationships between the number of vertices in the graph, the number of firefighters placed per turn, and the number of edges attached to the vertex at which the fire began. These results could be generalized so as to assist in determining where vaccinations would be best delivered so as to stop a pandemic, which waterways are most critical in monitoring for invasive species, and other situations where a harmful substance is spreading through a network.