# FPT Algorithms for Diverse Collections of Hitting Sets
## 1 Introduction
### Our Problems and Results  
In this work, we focus on diverse versions of two minimization problems, _d_-Hitting Set and Feedback Vertex Set, whose solutions are subsets of a finite set. _d_-Hitting Set is in fact a _class_ of such problems which includes Vertex Cover, as we describe below. We will consider two natural diversity measures for these problems: the minimum Hamming distance between any two solutions, and the sum of pairwise Hamming distances of all the solutions. The _Hamming distance_ between two sets \(S\) and \(S^{\prime}\), or _the size of their symmetric difference_, is  
\[d_{H}(S,S^{\prime}):=|(S\setminus S^{\prime})\cup(S^{\prime}\setminus S)|.\]  
We use  
\[\operatorname{div}_{\text{min}}(S_{1},\dots,S_{r}):=\min_{1\leq i<j\leq r}d_{ H}(S_{i},S_{j}) \tag{1}\]  
to denote the minimum Hamming distance between any pair of sets in a collection of finite sets, and  
\[\operatorname{div}_{\text{total}}(S_{1},\dots,S_{r}):=\sum_{1\leq i<j\leq r}d_ {H}(S_{i},S_{j}) \tag{2}\]  
to denote the sum of all pairwise Hamming distances. (In Section 5, we will discuss some issues with the latter formulation.) A _feedback vertex set_ of a graph \(G\) is any subset \(S\subseteq V(G)\) of the vertex set of \(G\) such that the graph \(G-S\) obtained by deleting the vertices in \(S\) is a _forest_; that is, it contains no cycle. Feedback Vertex Set  
**Input:** A graph \(G\). **Solution:** A feedback vertex set of \(G\) of the smallest size. More generally, a _hitting set_ of a collection \(\mathcal{F}\) of subsets of a universe \(U\) is any subset \(S\subseteq U\) such that every set in the family \(\mathcal{F}\) has a non-empty intersection with \(S\). For a fixed positive integer \(d\), the _d_-Hitting Set problem asks for a hitting set of the smallest size of a family \(\mathcal{F}\) of \(d\)-sized subsets of a finite universe \(U\):  
\[d\text{-Hitting Set}\]  
**Input:** A finite universe \(U\) and a family \(\mathcal{F}\) of subsets of \(U\), each of size at most \(d\). **Solution:** A hitting set \(S\) of \(\mathcal{F}\) of the smallest size. Observe that both Vertex Cover and Feedback Vertex Set are special cases of finding a smallest hitting set for a family of subsets. Vertex Cover is also an instance of _d_-Hitting Set, with \(d=2\): the universe \(U\) is the set of vertices of the input graph and the family \(\mathcal{F}\) consists of all sets \(\{v,w\}\), where \(vw\) is an edge in \(G\). There is no obvious way to model Feedback Vertex Set as a _d_-Hitting Set instance, however, because the cycles in the input graph are not necessarily of the same size. In this work, we consider the following problems in the Diverse \(X\) paradigm. Using \(\operatorname{div}_{\text{total}}\) as the diversity measure, we consider Diverse \(d\)-Hitting Set and Diverse Feedback Vertex Set, where \(X\) is \(d\)-Hitting Set and Feedback Vertex Set, respectively. Using \(\operatorname{div}_{\text{min}}\) as the diversity measure, we consider Min-Diverse \(d\)-Hitting Set and Min-Diverse Feedback Vertex Set, where \(X\) is \(d\)-Hitting Set and Feedback Vertex Set, respectively. In each case, we show that the problem is fixed-parameter tractable (\(\mathsf{FPT}\)), with the following running times:  
**Theorem 1**. : Diverse \(d\)-Hitting Set _can be solved in time \(r^{2}d^{kr}\cdot|U|^{O(1)}\)._  
**Theorem 2**. : Diverse Feedback Vertex Set _can be solved in time \(2^{kr}\cdot n^{O(1)}\)._  
**Theorem 3**. : Min-Diverse \(d\)-Hitting Set _can be solved in time_  
* \(2^{kr^{2}}\cdot(kr)^{O(1)}\) _if_ \(|U|<kr\) _and_
* \(d^{kr}\cdot|U|^{O(1)}\) _otherwise._  
**Theorem 4**. : Min-Diverse Feedback Vertex Set _can be solved in time \(2^{kr\cdot\max(r,7+\log_{2}(kr))}\cdot(nr)^{O(1)}\)._  
Defining the diverse versions Diverse Vertex Cover and Min-Diverse Vertex Cover of Vertex Cover in a similar manner as above, we get  
**Corollary 1**. : Diverse Vertex Cover _can be solved in time \(2^{kr}\cdot n^{O(1)}\).