# FPT Algorithms for Diverse Collections of Hitting Sets
## 4 Diverse Feedback Vertex Set
Thus, either it has a neighbor in \(B\), or, as \(v\) is a deepest leaf, it has another child, say \(w\) that is also a leaf in \(G^{\prime}[C]\), and \(w\) has therefore a neighbor in \(B\). We branch on the at most \(2^{3}=8\) possibilities to allocate \(v\), \(p\), and \(w\) if considered, between \(A\) and \(B\), taking care not to produce a cycle in \(B\). In both cases, either we put at least one vertex in \(A\), and so \(|A|\) increases by one, or all considered vertices are added to \(B\). In the latter case, the considered vertices are connected, at least two of them have a neighbor in \(B\), and no cycles were created; therefore, the number of components in \(B\) drops by one. Thus, \(|A|-\texttt{cc}(B)\) increases by at least one. As \(-k\leq|A|-\texttt{cc}(B)\leq k\), there can be at most \(2k\) branching steps. Since we branch at most \(2k\) times and at each branch we have at most \(2^{3}\) possibilities, the branching tree has at most \(2^{6k}\) leaves. Thus, for each of the at most \(2^{k}\) subsets \(F^{\prime}\) of \(F\), we add at most \(2^{6k}\) elements to \(\mathcal{S}\). It is clear that we have obtained all solutions of FVS and they are described by the classes of FVS solutions in \(\mathcal{S}\), which is of size \(2^{7k}\). Proof of Theorem 2.: We generate all \(2^{7k\tau}\)\(r\)-tuples of the classes of solutions given by Lemma 2, with repetition allowed. We now consider each \(r\)-tuple \(((S_{1},\ell_{1}),(S_{2},\ell_{2}),\ldots,(S_{r},\ell_{r}))\in\mathcal{S}^{r}\) and try to pick an appropriate solution \(T_{i}\) from each class of solutions \((S_{i},\ell_{i})\), \(i\in[1,k]\), in such a way that the diversity of the resulting tuple of feedback vertex sets \((T_{1},\ldots,T_{r})\) is maximized. The network of Section 3.1 must be adapted to model the constraints resulting from solution classes. Let \((S,\ell)\) be a solution class, with \(|S|=b\). For our construction, we just need to know the family \(\{\,\ell(v)\mid v\in S\,\}=\{L_{1},L_{2},\ldots,L_{b}\}\) of disjoint nonempty vertex sets. The solutions that are described by this class are all sets that can be obtained by picking at least one vertex from each set \(L_{q}\). Figure 2 shows the necessary adaptations for _one_ solution \(T=T_{i}\). In addition to a single node \(T\) that is either directly of indirectly connected to all nodes \(V_{1},\ldots,V_{n}\), like in Figure 1, we have additional nodes representing the sets \(L_{q}\). For each vertex \(j\) that appears in one of the sets \(L_{q}\), there is an additional node \(U_{j}\) in an intermediate layer of the network. The flow from \(s\) to \(L_{q}\) is forced to be equal to \(1\), and this ensures that at least one element of the set \(L_{q}\) is chosen in the solution. Here, it is important that the sets \(L_{q}\) are disjoint. A similar structure must be built for each set \(T_{1},\ldots,T_{r}\), and all these structures share the vertices \(s\) and \(V_{1},\ldots,V_{n}\). The rightmost layer of the network is the same as in Figure 1.  
The initial flow is not so straightforward as in Section 3.1 but is still easy to find. We simply saturate the arc from \(s\) to each of the nodes \(L_{q}\) in turn by a shortest augmenting path. Such a path can be found by a simple reachability search in the residual network, in \(O(rn)\) time. The total running time \(O(kr^{2}n)\) from Section 3.1 remains unchanged.