# FPT Algorithms for Diverse Collections of Hitting Sets
## 4 Diverse Feedback Vertex Set
For each subset \(F^{\prime}\subseteq F\), we initiate a branching process by setting \(A:=F^{\prime}\), \(B:=F-F^{\prime}\), and \(G^{\prime}:=G\). Observe that, initially, as \(B\subseteq F\) and \(|F|\leq k\), the graph \(G[B]\) has at most \(k\) components. In the branching process, we will add more vertices to \(A\) and \(B\), and we will remove vertices and edges from \(G^{\prime}\), but we will maintain the property that \(A\subseteq V(G^{\prime})\) and \(B\subseteq V(G^{\prime})\). The set \(C\) will always denote the vertex set \(V(G^{\prime})\setminus(A\cup B)\). Note that \(G^{\prime}[C]\) is initially a forest; we ensure that it always remains a forest. We also initialize a function \(\ell\colon V(G)\to 2^{V(G)}\) by setting \(\ell(v)=\{v\}\) for each \(v\in V(G)\). This function will keep information about vertices that are deleted from \(G\). While searching for a feedback vertex set, we consider only feedback vertex sets that contain all vertices of \(A\) but no vertex of \(B\). Vertices in \(C\) are still undecided. The function \(\ell\) will maintain the invariant that, for each \(v\in V(G^{\prime})\), \(\ell(v)\cap V(G^{\prime})=\{v\}\), and, for each \(v\in C\), all vertices of \(\ell(v)\) intersect at exactly the same cycles in \(G\setminus A\). Moreover, for each \(v\in A\), the value \(\ell(v)\) is fixed and will not be modified anymore in the branching process. During the branching process, we will progressively increase the size of \(A\), \(B\), and the sets \(\ell(v)\), \(v\in V(G)\). By _reducing_\((G^{\prime},A,B,\ell)\), we mean that we apply the following rules exhaustively. * If there is a \(v\in C\) such that \(\delta_{G^{\prime}[B\cup C]}(v)\leq 1\), we delete \(v\) from \(G^{\prime}\). * If there is an edge \(\{u,v\}\in E(G^{\prime}[C])\) such that \(\delta_{G^{\prime}[B\cup C]}(u)=\delta_{G^{\prime}[B\cup C]}(v)=2\), we contract \(u\) in \(G^{\prime}\) and set \(\ell(v):=\ell(v)\cup\ell(u)\). These are classical preprocessing rules for the Feedback Vertex Set problem; see, for instance, ([22], Section 9.1). Indeed, vertices of degree one cannot appear in a cycle, and consecutive vertices of degree 2 hit exactly the same cycles. After this preprocessing, there are no adjacent degree-two vertices and no degree-one vertices in \(C\). (Degrees are measured in \(G^{\prime}[B\cup C]\)). We start to describe the branching procedure. We work on the tuple \((G^{\prime},A,B,\ell)\). After each step, the value \(|A|-\texttt{cc}(B)\) will increase, where \(\texttt{cc}(B)\) denotes the number of connected components of \(G^{\prime}[B]\). At each step of the branching, we do the following. If \(|A|>k\) or if \(G^{\prime}[B]\) contains a cycle, we immediately stop this branch as there is no solution to be found in it. If \(A\) is a feedback vertex set of size at most \(k\), then \((A,\ell|_{A})\) is a class of FVS solutions, we add it to \(\mathcal{S}\) and stop working on this branch. Otherwise, we reduce \((G^{\prime},A,B,\ell)\). We pick a deepest leaf \(v\) in \(G^{\prime}[C]\) and apply one of the two following cases, depending on the vertex \(v\):  
* **Case 1:** The vertex \(v\) has at least two neighbors in \(B\) (in the graph \(G^{\prime}\)). If there is a path in \(B\) between two neighbors of \(v\), then we have to put \(v\) in \(A\), as otherwise this path together with \(v\) will induce a cycle. If there is no such path, we branch on both possibilities, inserting \(v\) either into \(A\) or into \(B\). * **Case 2:** The vertex \(v\) has at most one neighbor in \(B\). Since \(v\) is a leaf in \(G^{\prime}[C]\), it has at most one neighbor also in \(C\). On the other hand, we know that \(v\) has degree at least 2 in \(G^{\prime}[B\cup C]\). Thus, \(v\) has exactly one neighbor in \(B\) and one neighbor in \(C\), for a degree of 2 in \(G^{\prime}[B\cup C]\). Let \(p\) be the neighbor in \(C\). Again, as we have reduced \((G^{\prime},A,B,\ell)\), the degree of \(p\) in \(G^{\prime}[B\cup C]\) is at least 3.