# FPT Algorithms for Diverse Collections of Hitting Sets
## 1 Introduction  
The typical approach in modeling a real-world problem as a computational problem has, broadly speaking, two steps: (i) abstracting the problem into a mathematical formulation that captures the crux of the real-world problem, and (ii) asking for a best solution to the mathematical problem. Consider the following scenario: Dr. \(\mathcal{O}\) organizes a panel discussion and has a shortlist of candidates to invite. From that shortlist, Dr. \(\mathcal{O}\) wants to invite as many candidates as possible, such that each of them will bring an individual contribution to the panel. Given two candidates, \(A\) and \(B\), it may not be beneficial to invite both \(A\) and \(B\), for various reasons: their areas of expertise or opinions may be too similar for both to make a distinguishable contribution, or it may be preferable not to invite more than one person from each institution. It may even be the case that \(A\) and \(B\) do not see eye-to-eye on some issues which could come up at the discussion, and Dr. \(\mathcal{O}\) wishes to avoid a confrontation. A natural mathematical model to resolve Dr. \(\mathcal{O}\)'s dilemma is as an instance of the Vertex Cover problem: each candidate on the shortlist corresponds to a vertex, and for each pair of candidates \(A\) and \(B\), we add the edge between \(A\) and \(B\) if it is _not_ beneficial to invite both of them. Removing a smallest _vertex cover_ in the resulting graph results in a largest possible set of candidates such that each of them may be expected to individually contribute to the appeal of the event. Formally, a _vertex cover_ of an undirected graph \(G\) is any subset \(S\subseteq V(G)\) of the vertex set of \(G\) such that every edge in \(G\) has at least one end-point in \(G\). The Vertex Cover problem asks for a vertex cover of the smallest size: \begin{tabular}{|l l|} \hline \multicolumn{2}{|c|}{Vertex Cover} \\
**Input:** & Graph \(G\). \\
**Solution:** & A vertex cover \(S\) of \(G\) of the smallest size. \\ \hline \end{tabular}   
While the above model does provide Dr. \(\[PERSON]{O}\) with a set of candidates to invite that is _valid_ in the sense that each invited candidate can be expected to make a unique contribution to the panel, a vast amount of _side information_ about the candidates is lost in the modeling process. This side information could have helped Dr. \(\mathcal{O}\) to get more out of the panel discussion. For instance, Dr. \(\mathcal{O}\) may have preferred to invite more well-known or established people over 'newcomers', if they wanted the panel to be highly visible and prestigious; or they may have preferred to have more 'newcomers' in the panel, if they wanted the panel to have more outreach. Other preferences that Dr. [PERSON]mathcal{O}\) may have had include: to have people from many different cultural backgrounds, to have equal representation of genders, or preferential representation for affirmative action; to have a variety in the levels of seniority among the attendants, possibly skewed in one way or the other. Other factors, such as the total carbon footprint caused by the participants' travels, may also be of interest to Dr. \(\mathcal{O}\). This list could go on and on. Now, it is possible to plug in some of these factors into the mathematical model, for instance by including weights or labels. Thus, a vertex weight could indicate 'how well-established' a candidate is. However, the complexity of the model grows fast with each additional criterion. The classic field of multicriteria optimization [1] addresses the issue of bundling multiple factors into the objective function, but it is seldom possible to arrive at a balance in the various criteria in a way which captures more than a small fraction of all the relevant side information. Moreover, several side criteria may be conflicting or incomparable (or both); consider in Dr. [PERSON]mathcal{O}\)'s case'maximizing the number of different cultural backgrounds' vs.'minimizing total carbon footprint'.