Lab Lunch: 8 October 2019 - Mary Cryan and Cat Wedderburn

Title: Firefighter Games

Abstract:

I will introduce the concept of a 'Firefighter Game', which models the scenario of a graph within or more 'burning' nodes which set neighbours alight, with one or more Firefighters having to choosing nodes to 'defend' (quench the fire at that point) in such a way as to minimize overall damage overtime. Because of the temporal aspect of the game this is a more difficult computational problem than it might seem, with minimizing #burnt-nodes' being NP-hard even on some very simple graphs.

After I discuss some of the initial concepts and results, Cat will present some initial results on minimal maximal damage (mmd) graphs and how they may model epidemiological problems.