The School of Computer Science is pleased to present…
The Graph Burning and Firefighter Problems
MSc Thesis Proposal by: Jilsa Chandarana
Date: Thursday, 11 July 2024
Time: 11:00 AM
Location: Essex Hall, Room 122
Abstract:
With the increasing usage of social media, the spread of information has become abundant. However, this surge in accessible news and updates has also heightened the risk of spreading rumors. In our research, we explore two problems related to this phenomenon: the graph burning problem and the firefighter problem.
We provide a comprehensive survey of the graph burning problem, a discrete-time process. Initially, all the vertices of the graph are unburned, and we start the fire at a single vertex. The fire then spreads to the adjacent vertices of the burned vertices, and at each step, we select a new vertex to burn. Our objective is to burn all the vertices in a minimum number of steps. We review various approximation algorithms and bounds, highlighting significant advancements over the past decade.
In the firefighter problem, a graph is given, and a fire starts from a subset of vertices. At each step, firefighters protect a certain number of vertices as the fire continues to spread to adjacent vertices. We investigate the distance-restricted firefighter problem within a finite (n x n) grid, focusing on scenarios where a single firefighter is constrained to move at most one-unit distance per step. We claim that, under these constraints, a maximum of n2/8 vertices can be saved.
Thesis Committee:
Internal Reader: Dr. Curtis Bright
External Reader: Dr. Dennis Borisov
Advisor: Dr. Ahmad Biniaz