# FPT Algorithms for Diverse Collections of Hitting Sets
## 6 Maximizing the Smallest Hamming Distance  
The undesired behavior highlighted in Section 5 is the fact that the collection that maximizes the sum of the Hamming distances uses several copies of the same set. In this section, we explore how to handle this unexpected behavior by changing the distance to the minimal Hamming distance between two sets of the collection. This modification naturally removes the possibility of selecting the same solution twice. We show how to solve Min-Diverse \(d\)-Hitting Set and \(r\)-Min-Diverse \(k\)-Feedback Vertex Set for this metric. **Theorem 3**: Min-Diverse \(d\)-Hitting Set _can be solved in time_  
* \(2^{br^{2}}\cdot(kr)^{O(1)}\) _if_ \(|U|<kr\) _and_
* \(d^{dr}\cdot|U|^{O(1)}\) _otherwise._  
Let \((U,\mathcal{F},k,r,t)\) be an instance of Min-Diverse \(d\)-Hitting Set where \(|U|=n\). If \(n<kr\), we solve the problem by complete enumeration: There are trivially at most \(2^{n}\) hitting sets of size at  
Figure 3: The \(r=6\) different vertex covers of size \(r-1=5\) in a path with \(2(r-1)=10\) vertices. most \(k\). We form all \(r\)-tuples \((T_{1},\ldots,T_{r})\) of them and select the one that maximizes \(\operatorname{div}_{\min}(T_{1},\ldots,T_{r})\). The running time is at most \(O((2^{n})^{r}r^{2}n)=O(2^{kr^{2}}kr^{3})\). We now assume that \(n\geq kr\). We use the same strategy as in Section 3: We generate all \(r\)-tuples \((S_{1},\ldots,S_{r})\) of _minimal solutions_ and try to augment each one to a \(r\)-tuple \((T_{1},\ldots,T_{r})\) such that, for each \(i\in[1,r]\), \(|T_{i}|\leq k\) and \(S_{i}\subseteq T_{i}\subseteq V(G)\) hold. The difference is that we try to maximize \(\operatorname{div}_{\min}(T_{1},\ldots,T_{r})\) instead of \(\operatorname{div}_{\text{total}}(T_{1},\ldots,T_{r})\) in the augmentation. Given that we have a large supply of \(n\geq kr\) elements in \(U\), this is easy. To each set \(S_{i}\), we add \(k-|S_{i}|\) new elements, taking care that we pick different elements for each \(S_{i}\) that are not in any of the other sets \(S_{j}\). The Hamming distance between two resulting sets is then \(d_{H}(T_{i},T_{j})=d_{H}(S_{i},S_{j})+(k-|S_{i}|)+(k-|S_{i}|)\), and it is clear that this is the largest possibly distance that two sets \(T_{i}^{\prime}\supseteq S_{i}\) and \(T_{j}^{\prime}\supseteq S_{j}\) with \(|T_{i}^{\prime}|,|T_{j}^{\prime}|\leq k\) can achieve. Thus, since our choice of augmentation individually maximizes each pairwise Hamming distance, it also maximizes the smallest Hamming distance. This procedure can be carried out in \(O(kr+n)=O(n)\) time. In addition, we need \(O(kr^{2})=O(n^{2})\) time to compute the smallest distance. Using Lemma 1, we construct the set \(\mathcal{S}\) of all minimal solutions of the \(d\)-Hitting Set instance \((U,\mathcal{F})\), each of size at most \(k\). We then go through every \(r\)-tuple \((S_{1},\ldots,S_{r})\in\mathcal{S}^{r}\) and augment it optimally, as just described. The running time is \(d^{kr}\cdot O(n^{2})\). Theorem 4.2: Min-Diverse Feedback Vertex Set _can be solved in time \(2^{kr\cdot\max(r\mathcal{F}+\log_{2}(kr))}\cdot(nr)^{O(1)}\)._  
Proof: Let \(G\) be a \(n\)-vertex graph. If \(n<kr\), we again solve the problem by complete enumeration: There are trivially at most \(2^{n}\) feedback vertex sets of size at most \(k\). We form all \(r\)-tuples \((T_{1},\ldots,T_{r})\) of them and select the one that maximizes \(\operatorname{div}_{\min}(T_{1},\ldots,T_{r})\). The running time is at most \(O((2^{n})^{r}r^{2}n)=O(2^{kr^{2}}r^{2}n)\). We assume now that \(n\geq kr\). As in Section 4, we construct a set \(\mathcal{S}\) of at most \(2^{\mathcal{F}k}\) classes of FVS solutions of \(G\), using Lemma 2. Then, we go through all \((2^{\mathcal{F}k})^{r}\)\(r\)-tuples of classes \(S=((S_{1},\ell_{1}),\ldots,(S_{r},\ell_{r}))\in\mathcal{S}^{r}\).