
\subsection*{NP-hardness}

In this section, we state the proof of Theorem 13.

\subsection*{No Polynomial Kernel}

In this section, we state the proof of Theorem 28. 

\subsubsection*{Correctness of the Algorithm} 

We first show that the quantity $p$ always decreases when we recurse. 

\begin{lemma}\label{lem:measure-drop}
Let ${\mathcal I}^\prime := {\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle = (\chi(G_i,\mathfrak{T}_i),s^\star,C = \{t^\star\}, k, g, P_i, Q_i, Y_i, \gamma_i)$ be an arbitrary but fixed instance constructed by Solve-\textsc{SACS-R}{}(${\mathcal I}$). Then, $|P_i| < |P|$.
\end{lemma}

\begin{proof}
The claim follows from the fact that $P_i = B_i$, and $({\mathcal T}_1(P),{\mathcal T}_2(P))$ is a non-trivial partition of $P$. 
\end{proof}

\begin{lemma}\label{lem:correct-f}
If ${\mathcal I}$ is a \textsc{Yes}{} instance of \textsc{SACS-R}{}, then our algorithm returns \textsc{Yes}{}.
\end{lemma}

\begin{proof} (Sketch.) The statement follows by induction on $p$, which allows us to assume the correctness of the output of the recursive calls.  The correctness of the base cases is easily checked. If ${\mathcal I}$ is a \textsc{Yes}{} instance admits a solution $\mathfrak{h}$, then it induces a partition ${\mathcal T}_1(P), {\mathcal T}_2(P)$ of $P$. We argue that this is always a non-trivial partition and is therefore considered by the algorithm. Indeed, suppose not. This would imply that $\mathfrak{h}$ places all its firefighters in $W_i$ for some $1 \leq i \leq q+1$. However, this implies that $D := \cup_{t \in P_i} \mathfrak{h}(t) \subseteq W_i$ is a $s-C$ separator in $G \setminus Y$ that is entirely contained in $W_i$, which contradicts the definition of a tight $s-C$ separator sequence. 

Now, define the labeling $\mathfrak{T}$ by projecting the signature of $\mathfrak{h}$ on ${\mathcal S}$. Clearly, this labeling is compatible with ${\mathcal T}_1(P)$ (by definition). We claim that all the instances ${\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$ are \textsc{Yes}{} instances. Indeed, it is easy to check that the projection of $\mathfrak{h}$ on the subgraph $G_i$ is a valid solution for the instance ${\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$. It follows that the algorithm returns \textsc{Yes}{} since these $(q+1)$ instances return \textsc{Yes}{} by the induction hypothesis. 
\end{proof}


For the remainder of our discussion on correctness, our goal will be to prove the following reverse claim.

\begin{lemma}\label{lem:correct-b}
If the output of the algorithm is \textsc{Yes}{}, then ${\mathcal I}$ is a \textsc{Yes}{} instance of \textsc{SACS-R}{}.
\end{lemma}



This lemma is shown by establishing that $\mathfrak{h}^\star$ is indeed a valid solution for \textsc{SACS}{}. We arrive at this conclusion by a sequence of simple claims. We fix the accepting path in the algorithm, that is, an appropriate partition of $P$ and the labeling $\mathfrak{T}$ on ${\mathcal S}$ that triggered \textsc{Yes}{} output. Our first claim says that the recursive instances respect the behavior dictated by the labeling that they were based on. 

\begin{lemma}\label{lem:burn}
Let $1 \leq i \leq q+1$ and $v \in {\mathcal S} \cap H_i$. If $\mathfrak{T}_i(v) = (\mathfrak{b},t)$, then in any partial strategy employed on the instance ${\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$ that saves the critical set, the vertex $v$ burns exactly at time step $t$.
\end{lemma}

\begin{proof}
Let $\mathfrak{h}^\prime$ be an arbitrary but fixed valid partial strategy for ${\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$ that saves the critical set. Assume that $v$ burns with respect to $\mathfrak{h}^\prime$. Let $t^\prime$ be the earliest time step at which $v$ burns with respect to  $\mathfrak{h}^\prime$. The graph $\chi(G_i,\mathfrak{T}_i)$ contains $(k+1)$ vertex-disjoint paths from the source to $v$ of length $t/2$, which ensures that $t^\prime \leq t$. However, if $t^\prime < t$, then the vertex $g$ catches fire at time step $2k-1$ because of the $(k+1)$ vertex-disjoint paths of length $k-t/2-1$ that are present from $v$ to $g$. This implies that $t^\star$ cannot be saved if $v$ burns earlier than $t$. The other case is that $v$ does not burn with respect to $\mathfrak{h}^\prime$. The only way for this to happen is if a firefighter is placed on $v$, however, since the instance has $k+1$ copies of $v$, we have that at least one copy of $v$ burns, and the claim follows. 
\end{proof}

Our next claim is that vertices that are labeled saved never burn with respect to $\mathfrak{h}^\star$.

\begin{lemma}\label{lem:save}
For any $v \in {\mathcal S}$, if $\mathfrak{T}(v) = \mathfrak{p}$, then $v$ does not burn with respect to $\mathfrak{h}^\star$.
\end{lemma}

\begin{proof}
We prove this by contradiction. Let $P$ be a path from $s$ to $v$ where all vertices on $P$ are burning. Let $v^\prime$ be the first vertex on this path which is such that $\mathfrak{T}(v^\prime) = \mathfrak{p}$, and let $u$ be the last vertex on this path which is before $v^\prime$ and that intersects a separator. Observe that $u$ is well-defined unless $v^\prime \in S_1$, which is a special case that we will deal with separately. Note that $u$ must be a vertex that is labeled as burned (by the choice of $v^\prime$). Therefore, the path from $u$ to $v$ is present in a recursive instance, where we know that $v^\prime$ is adjacent to a critical vertex, which contradicts the fact that we defined $\mathfrak{h}^\star$ based on valid strategies that save critical sets in the recursive instances. If $v^\prime \in S_1$ and $u$ is not well-defined, then observe that there is a direct path from $s$ to $v^\prime$ in the first recursive instance, and the same argument applies. 
\end{proof}


We finally show, over the next two claims, that the function $\mathfrak{h}^\star$ is a valid strategy that saves the critical set. 

\begin{lemma}\label{lem:valid}
	The function $\mathfrak{h}^\star$ is a valid partial strategy over $(P \cup Q)$ for the instance ${\mathcal I}$. 
\end{lemma}
\begin{proof} We prove this by contradiction, and we also assume that Lemma~\ref{lem:correct-b} holds for all recursive instances (by induction on $p$). If $\mathfrak{h}^\star$ is not a valid strategy, then there exists some $1 \leq i \leq q+1$ for which there is a vertex $v \in W_i$ and a time step $t \in B_i$ such that $\mathfrak{h}^\star(t) = v$ and $v$ is burning at time step $t$. Consider the path $P$ from $s$ to $v$. Let $u$ be the last vertex on the path $P$ that intersects $S_{i-1} \cup S_i$. Observe that $u$ is a vertex that is either labeled by $(\mathfrak{b},t)$ or $\mathfrak{p}$. This leads to the following two scenarios:

\begin{itemize}
	\item In the first case, the part of the path from $u$ to $v$ is present in the instance ${\mathcal I}\langle i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$, because of the agreement of $\mathfrak{h}^\star$ and $\mathfrak{h}[i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}]$ and Lemma~\ref{lem:burn}. Therefore, $\mathfrak{h}[i,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}]$ was not a valid firefighting strategy.
	\item The second situation implies that a vertex labeled protected is burning in ${\mathcal I}$ when $\mathfrak{h}^\star$ is employed, which contradicts Lemma~\ref{lem:save}. 
\end{itemize} 
\end{proof}


\begin{lemma}\label{lem:safe}
	The partial strategy $\mathfrak{h}^\star$ saves the set $C$ in the instance ${\mathcal I}$. 
\end{lemma}
\begin{proof}(Sketch.) The proof of this is similar to the proof of Lemma~\ref{lem:valid}. Any burning path $P$ from $s$ to any vertex in $C$ must intersect $S_q$. We let $v$ be the last vertex from $S_q$ on $P$, and observe that $v$ must have a $(\mathfrak{b},t)$. Therefore, the path from $v$ to the vertex in $C$ exists in ${\mathcal I}\langle q+1,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}_i \rangle$, and also burns in the same fashion, since $\mathfrak{h}^\star$ agrees with $\mathfrak{h}[q+1,{\mathcal T}_1(P),{\mathcal T}_2(P),\mathfrak{T}]$. Again, this contradicts the accuracy of the algorithm on the recursive instance. 
	\end{proof}

The proof of Lemma~\ref{lem:correct-b} now follows from Lemmas~\ref{lem:valid} and~\ref{lem:burn}.

\input{rta.tex}









\section{Introduction}
\label{sec:introduction}
\input{ffcs-intro.tex}

\section{Preliminaries}
\label{sec:prelims}
\input{ffcs-prelims}

\section{The Parameterized Complexity of Saving a Critical Set}

\input{ffcs-section3-overview.tex}

\subsection{The FPT Algorithm}
\label{sec:FPTAlg}
\input{ffcs-fpt.tex}


\subsection{A Faster Algorithm For Trees}
\label{sec:Trees}
\input{ffcs-trees.tex}


\subsection{No Polynomial Kernel, Even on Trees}
\label{sec:npk}
\input{ffcs-npk.tex}

\section{The Spreading Model}
\label{sec:gen}
\input{ffcs-generalized.tex}

\section{Summary and Conclusions}

\input{ffcs-conclusions.tex}





\subsubsection*{Running Time Analysis} 





We show that our algorithm runs in time $f(k)^{p^2}O(n^2m)$, where $f(k) = k^{O(k)}$.  Indeed, observe that the running time of the algorithm is governed by the following recurrence:

\[ T(n,m,k,p) \leq O(n^2mp) + (p+k+1)^{kp}\sum_{i=1}^{q+1}T(n_i,m_i,k,p_i) \]




where the term $(p+k+1)^{kp}$ denotes an upper bound on the product of the total number of non-trivial partitions of $P$ into $(2q+1)$ parts and the total number of legitimate labelings of ${\mathcal S}$ compatible with ${\mathcal T}_1(P)$. The first term accounts for checking the base cases and the running time of computing a tight separator sequence of order $p$ (see Lemma~\ref{lem:compute-sep-seq}). Since $p$ is always at most $k$, we rewrite the recurrence as 

\[ T(n,m,k,p) \leq O(n^2mp) + f(k)^{p}\sum_{i=1}^{q+1}T(n_i,m_i,k,p_i), \]



  
 where $f(k)=k^{O(k)}$. Furthermore, observe that $\sum_{i=1}^{q+1} n_i \leq n + pk$. The first inequality follows from the fact that every vertex in ${\mathcal S}$ appears in at most two recursive instances. The first occurrence is counted in $n$, while all the second occurrences combined amount to at most $pk$. 

Finally, recall that $p_i < p$ by Lemma~\ref{lem:measure-drop} and  $p \leq k$ by definition (since $P \subseteq [2k]_{\mathcal O}$). Therefore, the depth of the recursion is bounded by $p$, and the time spent at each level of recursion is  proportional to $k^{O(kp)}n^2m$. This implies the claimed running time. 

Based on the analysis above and Lemmas~\ref{lem:correct-f} and \ref{lem:correct-b}, we have thus demonstrated the main result of this section.

\begin{theorem}
	\textsc{SACS}{} is \textrm{\textup{FPT}}\xspace{} and has an algorithm with running time  $f(k)O(nm^2)$, where $f(k) = k^{O(k^3)}$.
\end{theorem}