---
# System prepended metadata

title: Untitled

---

Some resources for Level 4 students on games on graphs:

Lately I’ve been spending some of my more algorithmic time on temporal and multilayer graphs and algorithms for them (e.g. https://arxiv.org/pdf/1805.06836.pdf, https://arxiv.org/abs/1802.05905) and on pursuit or spreading games for graphs.  

Pursuit and spreading games are games like:
- firefighter, where a fire starts somewhere on the graph and at each turn we get some budget to defend a number of vertices.  We can ask algorithmic questions like: how many vertices can we save?  Can we contain things in finite time on an infinite graph?  This last week I’ve been thinking about a version in which the defence also spreads, like an infectious vaccine or a competing disease.  A somewhat old survey here:  https://ajc.maths.uq.edu.au/pdf/43/ajc_v43_p057.pdf and a recent paper of mine with a grad student here: https://arxiv.org/abs/2202.12599
- cops and robbers, where some number of cops chase some number of robbers around a graph.  There are a million variants with stealthy robbers or cops that cannot visit some vertices, etc. Here’s a blog post with some links: https://anthonybonato.com/2018/04/04/a-new-prehistory-of-cops-and-robbers/
- graph burning, where we are trying to burn a graph as fast as possible by setting fires that spread on each turn.  Here’s a fairly recent survey:  https://arxiv.org/abs/2009.10642
- localisation, where probes (or cops, if we want to be analogous with cops and robbers) try to find a hidden agent by getting a distance vector from a selected set of probe locations.  Here’s a related paper:  https://arxiv.org/abs/2105.09806, and a research seminar: https://www.youtube.com/watch?v=5cDLI-g5Y4s
    - I've also thought a bit about a static version where the probe location is fixed at the start of the game, some old and draft notes on preliminary work here:  https://drive.google.com/file/d/1nvS1jPLinyMFp3Xx3aVDMhQD7wh8zAw7/view?usp=sharing


And some notes from a summer school I just did on temporal graph firefighter:
https://hackmd.io/@magicicada/ss_gsac_2022