---
tags: gsac, summer school, temporal, firefighter, spreading
---

# Introductions and Plan:
Person introductions

Hi, I'm Jess!

Who else is here?

## The Plan (all adjustable!)
- Firefighter
- Temporal graphs
- Temporal Firefighter
- Existing results on hardness and tractability
- Ideas around restricted temporal structures
- Firebreak
- Directions for questions

Very informal!
Any requests?

Note: throughout borrow heavily from work by Sam Hand, e.g.: https://arxiv.org/abs/2202.12599

---

# Firefighter
(figures and some examples from https://www.unf.edu/~wkloster/3210/FireSurvey.pdf)

We start with a graph and a specified root where a fire starts. On each turn:
- we defend $b$ vertices
- then the fire spreads: every undefended vertex beside a burning vertex becomes burning
- repeat
Burning vertices burn forever, defended vertices are defended forever.

Example:

---

What are the questions?
- Given a graph, a root, and a budget: can we save at least $k$ vertices? (**Classic Firefighter**)
- Given a graph, a root, and a budget: can we save some particular set of vertices?
- What are the most defensible graphs?
- In an infinite graph, can we *contain* the fire?
- In an infinite graph, can we save some fraction?

More formally: work with $MVS(G, r, 1)$ - the maximum number of vertices saved if the fire breaks out in graph $G$ at vertex $r$ and you can defend 1 vertex per timestep:


We can use this notation more generally: $MVS(G, F, b)$ is the max number of vertices saved when:
- fire breaks out at vertices in $F$ in graph $G$
- we defend $b$ vertices at each time step

---

Various algorithmic results known, including:
- NP-hard on bipartite graphs
- NP-hard on trees of max degree 3
- Polytime on above if fire starts at vertex of max degree 2
- strategy at: https://www.sciencedirect.com/science/article/pii/S0012365X0600776X
- crux: argue that we can always defend beside a burning vertex, can always limit burning to 'one path' - just need to identify which one is best. (draw example sketch on board?)
- Polytime on interval graphs, split graphs, permutation graphs, and $P_k$-free graphs for fixed $k$ (Fomin paper: https://www.sciencedirect.com/science/article/pii/S0304397515010853).
- Greedy algorithm gives a 1/2-approx on trees

Reproduced roughly from Fomin:

---
Thought experiment: Most defensible graphs

Over all connected graphs on $n$ vertices, assume optimal (for the fire) fire placement and optimal defence, what graphs have the least burning?

This depends on the number of fires and the budget to defend!
- with one fire and one firefighter?

(note paper and problems with finding it:
S. Finbow, B. Hartnell, Q. Li, and K. Schmeisser, On minimizing the effects of fire or a virus on a network, Journal of Combinatorial Mathematics and Combinatorial Computing 33)

**To my knowledge nothing is known on this in te temporal setting**

---

Containability on infinite graphs:
- Say we have an infinite grid (e.g. square grid, hex, etc):
- Can $d$ firefighters stop the fire within finite time?

Some work on containment on infinite grids:
- Gavenčiak, Kratochvíl, Prałat: Firefighting on square, hexagonal, and triangular grids, 2014
- Dean et al: Firefighting on the Hexagonal Grid and on Infinite Trees, 2020

Both describe strategies involving playing along rays in the plane, and then bending those rays.

Let's have a look at square and hex grid examples to get thinking:



From Gavenčiak, Kratochvíl, Prałat: Firefighting on square, hexagonal, and triangular grids, 2014 - one firefighter per trun plus two extra


Resources;
- https://www.unf.edu/~wkloster/3210/FireSurvey.pdf
- https://www.sciencedirect.com/science/article/pii/S0012365X0600776X
- https://www.sciencedirect.com/science/article/pii/S0304397515010853
- A newer review, I have not inspected: https://dspace.library.uvic.ca/bitstream/handle/1828/13360/Wagner_Connor_M.Sc._2021.pdf?sequence=6

---
# Temporal graphs

Many networks from data have time information - temporal graphs can incorporate this.

Many notation options, but one is:

A temporal graph is a pair $(G, \lambda)$ where $G$ is the underlying static graph $(V, E)$ and $\lambda : E \to 2^\mathbb{N}$ is the time-labeling function, assigning to each edge a set of timesteps at which it is active.


---

**Problems can become harder once time is involved.**

An example: defining a shortest path is not straightforward and both foremost and fastest path computation is hard.

To give an intuition for what these types of paths are:

(copied from https://arxiv.org/abs/2006.08668)

Temporal betweenness-related discussion: https://arxiv.org/abs/2006.08668

---

# Firefighter on temporal graphs
We can play firefighter on a temporal graph - say everying stays the same as the classic, except fires can only spread over edges when they are active


Hard on temporal cliques:

And other reductions give us hardness on trees of limited lifetime.

---
**A positive result** on graphs of max degree three when starts at degree two (copy-pasted and re-chopped from Sam's paper):

Intuitively the same as in the static case: as soon as the fire reaches a vertex at which the temporal nature of the graph delays its spread, it is possible to contain it, and in an optimal strategy the fire will spread along a path to such a vertex at a rate of one vertex per timestep, just as in \textsc{Firefighter}.

More formally:

Define three sets: $V_0$, $V_1$, and $V_c$.

- $V_0$ and $V_1$ are the sets of all vertices $u$ that at time $\dist(r, u)+1$ are temporally adjacent, respectively, to $0$ and $1$ vertices not on the shortest underlying path between $r$ and $u$.
- $V_c$ is the set of all vertices that lie on a cycle and are not in $V_0$ or $V_1$. Additionally for any vertex $u$, $C(u)$ denotes the length of the shortest cycle containing $u$.

Strategy $S$ operates by first finding a vertex $u \in V_0 \cup V_1 \cup V_c$ that minimizes the function $f(u)$, defined below.

\[
f(u) =
\begin{cases}
\dist(r, u) + 1 & \text{if } u \in V_0 \cup V_1 \\
\dist(r, u) + C(u) - 1 & \text{if } u \in V_c
\end{cases}
\]
If $u \in V_0 \cup V_1$, then let $P$ be the shortest path from $r$ to $u$ on the underlying graph $G$. As $u$ minimizes $f$, this path will always be temporally admissible and have an arrival time equal to its length.

The strategy is then to always defend the vertex adjacent to the fire that does not lie on $P$, up until turn $f(u)$. On turn $f(u)$ a non-burning neighbour of $u$ should be defended, prioritising a temporally adjacent neighbour if one exists. If there is a further non-burning neighbour of $u$, this should be defended on turn $f(u)+1$. Once the fire stops spreading, the burnt vertices will be all those on $P$, meaning that in total $f(u)$ vertices will be burnt.

---

**But many negative results**: hard on split, permutation, AT-free, etc.
Overall restricting underlying graph not very successful.

---

Restricting temporal structure slightly more exciting, but existing result is technical and complicated!


Temporal Firefighter FPT by this measure.


# Firebreak

I want to mention a related problem we defined to consider a less temporal version of firefighter.

Here the firefighters are all active only at the first timestep.

- Given a graph $G = (V, E)$, a root $v_f$, a budget $d$, and a target $t$: can we immediately defend $d$ vertices to save $t$? or:
- Given a graph $G = (V, E)$, a root $v_f$, a budget $d$, and a target $t$: is there a separator in $G$ of size $d$ such that at least $t$ vertices are separated from $v_f$

Initially I though that this might be efficiently solvable as a min cut problem, but not so!

NP-Hardness via the $t-$Way Vertex Cut problem

- Given a graph $G = (V, E)$, positive integers $k$ and $t$
- Does V contain a $S$ of size at most $k$ such that $G - S$ has at least $t$ components?

Efficiently solvable on trees - essentially choose the neighbours of the root with the greatest number of descendants.

With some machinery, can show tractable on graphs of bounded treewidth.

Firebreak on interval graphs
Interval graphs are graphs with a bijection between their vertices and intervals on a line: two vertices are adjacent iff their intervals intersect.


We can use two vertical lines to sweep looking for suitable separators - a similar idea works for some other types on intersection representation like permutation graphs.

In the temporal case: I suspect there is no difference to the static case, but would be nice to confirm.

# Suggestions of questions to work on:

### Starters and Examples:
- Construct a temporal firefighter instance with defense budget $b$ on which only $b$ vertices do not burn
- Construct a temporal firefighter instance on which the underlying graph is a tree but a large number of vertices burn
- As previous, but with a constrained maximum temporal degree.
- Identify a 'greedy' approach to defense on temporal firefighter (or a variant, or Firebreak, etc). Can you produce examples of graphs on which your greedy strategy is arbitrarily wrong, or on which you can make approximation guarantees?

### Temporal Firebreak
- Show Temporal Firebreak is hard on temporal cliques.
- When is Temporal Firebreak polytime on temporal graphs? (I suspect there is no difference to the static case)
- What if we have an edge-time-defence budget instead of a vertex defense budget?

### Edge defence and other defence variants
- Which temporal firefighter results carry over to temporal edge firefighter, or temporal edge-time firefighter?
- Show infectious protection temporal firefighter is hard.
- And also any initial results on infectious protection temporal firefighter - e.g. paths? Is there a relationship to graph burning here?

### Spread variants
- Consider Fizzling Temporal Firefighter: here, a fire will burn out at a vertex some specified time after the vertex catches fire. (modelling e.g. a maximum infectious period if the fire is a disease). What is the status of this problem in general, or on restricted classes (e.g. cliques, trees, max degree)?

### Patterns in timings (e.g. periodic)
- Say we are working in a infinite grid. What patterns of edge-times make an instance containable with one firefighter (or two, etc)? E.g. what if we are working in a square grid and horizontal edges are active at odd times, vertical at even? Or, what if all edges are active at all times, except a single column somewhere is not active at a single time step? Consider other restrictions.
- Consider other temporal graphs with preiodic or restricted timings, perhaps starting points in hypercubes, trees, products of graphs? Interval graphs or permutation graphs in which timings have some correspondance to a representation?
- note periodic cops-and-robbers paper: https://arxiv.org/abs/2104.08616

### Something I'd really like to know:
- What is the complexity of Temporal Firefighter on temporal graphs when there is a constant bounded number of edges active at each timestep? Say on a tree with degree at most three?
- Even on restricted classes?
- Note we'd need to bound both degree and max activity on a timestep.