The Firebreak problem
David Pike and Andrea Burgess (Memorial University of Newfoundland and University of New Brunswick Saint John)
Abstract: Suppose a network is represented by a graph $G$. A fire (or some sort of contagion) breaks out at a vertex. Firefighters then respond by establishing a single firebreak consisting of $k$ other vertices of $G$. The fire cannot burn or pass through these $k$ protected vertices; however, the fire subsequently spreads to all vertices it can reach without passing through the firebreak. A natural question arises: how many vertices can be prevented from burning?
We discuss how this problem came to our attention, how the research process evolved, and how collaborators became engaged. We also delve into the scientific aspects of the problem, with emphasis on computational complexity. In general, the associated decision problem is NP-complete, but it is solvable in polynomial time for certain graph classes. In addition, we will discuss potential applications.
This is joint work with Kathleen Barnetson, Jessica Enright, Jared Howell and Brady Ryan.
combinatorics
Audience: researchers in the topic
Carleton Combinatorics Meeting 2021
Series comments: See the external webpage for more details: people.math.carleton.ca/~dthomson/CCM2021
To contact, please use CCM2021@math.carleton.ca and prefix your subject with "[CCM2021-request]"
| Organizers: | Daniel Panario, David Thomson*, Qiang Wang |
| *contact for this listing |