# FPT Algorithms for Diverse Collections of Hitting Sets
## 4 Diverse Feedback Vertex Set  
A _feedback vertex set_ (FVS) (also called a _cycle cutset_) of a graph \(G\) is any subset \(S\subseteq V(G)\) of vertices of \(G\) such that every cycle in \(G\) contains at least one vertex from \(S\). The graph \(G-S\) obtained by deleting \(S\) from \(G\) is thus an acyclic graph. Finding an FVS of small size is an NP-hard problem [25] with a number of applications in Artificial Intelligence, many of which stem from the fact that many hard problems become easy to solve in acyclic graphs. An example for this is the Propositional Model Counting (or #SAT) problem that asks for the number of satisfying assignments for a given CNF formula, and has a number of applications, for instance in planning [26; 27] and in probabilistic inference problems such as Bayesian reasoning [28; 29; 30; 31]. A popular approach to solving #SAT consists of first finding a small FVS \(S\) of the CNF formula. Assigning values to all the variables in \(S\) results in an acyclic instance of CNF. The algorithm assigns all possible sets of values to the variables in \(S\), computes the number of satisfying assignments of the resulting acyclic instances, and returns the sum of these counts [32]. In this section, we focus on the Diverse Feedback Vertex Set problem and prove the following theorem. **Theorem 2**. : Diverse Feedback Vertex Set _can be solved in time \(2^{7 kr}\cdot n^{O(1)}\)._  
In order to solve \(r\)-Diverse \(k\)-Feedback Vertex Set, one natural way would be to generate every feedback vertex set of size at most \(k\) and then check which set of \(k\) solutions provide the required sum of Hamming distances. Unfortunately, the number of feedback vertex sets is not \(\mathsf{FPT}\) parameterized by \(k\). Indeed, one can consider a graph containing \(k\) cycle of size \(\frac{n}{k}\), leading to \(\binom{n}{k}^{k}\) different feedback vertex sets of size \(k\). We avoid this problem by generating all such small feedback vertex sets up to some equivalence of degree two vertices. We obtain an exact and efficient description of all feedback vertex sets of size at most \(k\), which is formally captured by Lemma 2. A _class of solutions_ of a graph \(G\), is a pair \((S,\ell)\) such that \(S\subseteq V(G)\) and \(\ell:S\to 2^{V(G)}\) is a function such that for each \(u\in S\), \(u\in\ell(u)\), and for each \(u,v\in S\), \(u\
eq v\), \(\ell(u)\cap\ell(v)=\emptyset\). Given a class of solutions \((S,\ell)\), we define \(\mathtt{sol}(S,\ell)=\{S^{\prime}\subseteq V(G):|S^{\prime}|=|S|\) and \(\forall v\in S,|S^{\prime}\cap\ell(v)|=1\}\). A _class of FVS solutions_ is a class of solutions \((S,\ell)\) such that each \(S^{\prime}\in\mathtt{sol}(S,\ell)\) is a feedback vertex set of \(G\). Moreover, if \(S^{\prime}\in\mathtt{sol}(S,\ell)\) and \(S^{\prime}\subseteq S^{\prime\prime}\subseteq V(G)\), we say that \(S^{\prime\prime}\) is _described_ by \((S,\ell)\). Note that \(S^{\prime\prime}\) is also a feedback vertex set. In a class of FVS solutions \((S,\ell)\), the meaning of the function \(\ell\) is that, for each cycle \(C\) in \(G\), there exists \(v\in S\) such that each element of \(\ell(v)\) hits \(C\). This allows us to group related solutions into only one set \(\mathtt{sol}(S,\ell)\). **Lemma 2**. : _Let \(G\) be a \(n\)-vertex graph. There exists a set \(\mathcal{S}\) of classes of FVS solutions of \(G\) of size at most \(2^{7k}\) such that each feedback vertex set of size at most \(k\) is described by an element of \(\mathcal{S}\). Moreover, \(\mathcal{S}\) can be constructed in time \(2^{7k}\cdot n^{O(1)}\)._  
Proof. : Let \(G\) be a \(n\)-vertex graph. We start by generating a feedback vertex set \(F\subseteq V\) of size at most \(k\). The current best deterministic algorithm for this by [PERSON] and [PERSON] [33] finds such a set in time \(3.62^{k}\cdot n^{O(1)}\). In the following, we use the ideas used for the iterative compression approach [34].