The Temporal Firefighter problem models the spread of a fire—or any contagion—through a network. Just as in the classical Firefighter problem, the goal is to protect as much of the network as possible by deploying defenses (e.g. firefighters, quarantines, barriers) at critical moments. In the temporal variant, edges appear and disappear over time, meaning the spread of the fire is governed not just by the graph's structure, but by its timing.

This setting captures more realistic scenarios found in dynamic networks, such as:

• Containing a virus in a transportation network where connections become available/disappear over time
• Preventing misinformation from spreading through (online) social networks
• Managing failures in time-dependent communication infrastructures

In each time step:

• The fire spreads from burning vertices along active edges to any unburnt and undefended neighbor.
• A firefighter can defend one vertex (or more, depending on variant), preventing it from burning.
• The process continues over the graph’s lifetime, and the goal is to maximize the number of saved vertices.

<aside> 💡

Definition.

Input: A rooted temporal graph $(\mathcal{G}, r)$ and an integer $h$.

Question: Does there exist a defense strategy that saves at least $h$ vertices, assuming the fire starts at vertex $r$?

</aside>

🔐 Key Variants

• Temporal Firefighter Reserve: Instead of placing a firefighter at every step, a budget increases over time (by 1 per step), and multiple defenses can be placed at once, respecting the current budget. This reflects scenarios where defense is more strategic and not necessarily continuous.

Literature on Temporal Firefighter

History of Research on Temporal Firefighter

🧠 Complexity and Results

• Hardness:
  • Temporal Firefighter is NP-complete even on very simple graph classes (e.g., stars, complete graphs with low snapshot degrees).
  • It remains hard even when the static Firefighter problem is tractable.
  • The problem is ParaNP-hard when parameterized by natural parameters like the temporal h-index (number of high-degree time-vertices).
• Tractability:
  • An FPT algorithm exists when parameterized by:
    • the vertex-interval-membership width (VIM) [Bumpus & Meeks]
    • the combined treewidth + max degree of the underlying static graph
• Intractability despite structure:
  • The problem is still NP-hard even on graphs of bounded TIM width and ≥-connected VIM width