# FPT Algorithms for Diverse Collections of Hitting Sets
## 7 Conclusions and Open Problems  
In this work, we have considered the paradigm of finding small diverse collections of reasonably good solutions to combinatorial problems, which has recently been introduced to the field of fixed-parameter tractability theory [21]. We have shown that finding diverse collections of \(d\)-hitting sets and feedback vertex sets can be done in FPT time. While these problems can be classified as FPT via the kernels and a treewidth-based meta-theorem proved in [21], the methods proposed here are of independent interest. We introduced a method of generating a maximally diverse set of solutions from a set that either contains all minimal solutions of bounded size (\(d\)-Hitting Set) or from a collection of structures that in some way _describes_ all solutions of bounded size (Feedback Vertex Set). In both cases, the maximally diverse collection of solutions is obtained via a network flow model, which does not rely on any specific properties of the studied problems. It would be interesting to see if this strategy can be applied to give FPT-algorithms for diverse problems that are not covered by the meta-theorem or the kernels presented in [21]. While the problems in [21] as well as the ones in Sections 3 and 4 seek to maximize the _sum_ of all pairwise Hamming distances, we also studied the variant that asks to maximize the _minimum_ Hamming distance, taken over each pair of solutions. This was motivated by an example where the former measure does not perform as intended (Section 5). We showed that also, under this objective, the diverse variants of \(d\)-Hitting Set and Feedback Vertex Set are FPT. It would be interesting to see whether this objective also allows for a (possibly treewidth-based) meta-theorem. In [21], the authors ask whether there is a problem that is in FPT parameterized by a solution size whose \(r\)-diverse variant becomes \(\mathsf{W}[\mathbf{1}]\)-hard upon adding \(r\) as another component of the parameter. We restate this question here. **Question 1** (Open Question [21]). : _Is there a problem \(\Pi\) with solution size \(k\), such that \(\Pi\) is FPT parameterized by \(k\), while Diverse \(\Pi\), asking for \(r\) solutions, is \(\mathsf{W}[\mathbf{1}]\)-hard parameterized by \(k+r\)?_  
To the best of our knowledge, this problem is still wide open. We believe that the \(\operatorname{div}_{\min}\) measure is more promising to obtain such a result rather than the \(\operatorname{div}_{\operatorname{total}}\) measure. A possible way to tackle both measures at once might be a parameterized (and strenghtened) analogue of the following approach that is well-studied in classical complexity. [PERSON] and [PERSON] propose a framework [35] to prove NP-completeness of finding a _second_ solution to an NP-complete problem. In other words, there are some problems where given one solution it is still NP-hard to determine whether the problem has a different solution. From a different perspective, one might want to identify problems where obtaining one solution is polynomial-time solvable, but finding a diverse collection of \(r\) solutions becomes NP-hard. The targeted running time should be FPT parameterized by \(r\) (and maybe \(t\), the diversity target) only. We conjecture that this is most probably NP- or \(\mathsf{W}[-]\) hard in general. However, we believe it is interesting to search for well-known problems where it is not the case. Conceptualization, [PERSON], L.J., T.M., G.P. and G.R. ; Methodology, [PERSON], L.J., T.M., G.P. and G.R. ; Investigation, [PERSON], L.J., T.M., G.P. and G.R. ; Writing-original draft preparation, [PERSON], L.J., T.M., G.P. and G.R. ; Writing-review and editing, [PERSON], L.J., T.M., G.P. and G.R. [PERSON] received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement No. 714704, and from Charles University student Grant No. SVV-2017-260452. [PERSON] is supported by the Bergen Research Foundation (BFS).