# FPT Algorithms for Diverse Collections of Hitting Sets
## 1 Introduction
As an alternative to optimization for such problems, [PERSON] proposed a \"Branch & Sample\" algorithm for generating a \"limited, representative sample of solutions, uniformly scattered over the entire solution space\" [10]. **The Diverse \(X\) Paradigm. ** [PERSON] has proposed _the Diverse \(X\) Paradigm_ as a solution for these issues and others [11]. In this paradigm, \"\(X\)\" is a placeholder for an optimization problem, and we study the complexity--specifically, the fixed-parameter tractability--of the problem of finding a few different good quality solutions for \(X\). Contrast this with the traditional approach of looking for just one good quality solution. Let \(X\) denote an optimization problem where one looks for a minimum-size subset of some set; Vertex Cover is an example of such a problem. The generic form of \(X\) is then: \begin{tabular}{|l l|} \hline  & & \\ \hline \multicolumn{2}{|c|}{\(X\)} \\
**Input:** & An instance \(I\) of \(X\). \\
**Solution:** & A solution \(S\) of \(I\) of the smallest size. \\ \hline \end{tabular}   
Here, the form that a \"solution \(S\) of \(I\)\" takes is dictated by the problem \(X\); compare this with the earlier definition of Vertex Cover. The _diverse_ variant of problem \(X\), as proposed by Fellows, has the form: \begin{tabular}{|l l|} \hline  & & Diverse \(X\) \\
**Input:** & An instance \(I\) of \(X\), and positive integers \(k,r,t\). \\
**Parameter:** & \((k,r)\) \\
**Solution:** & A set \(\mathcal{S}\) of \(r\) solutions of \(I\), each of size at most \(k\), such that a _diversity measure_ of \(\mathcal{S}\) is at least \(t\). \\ \hline \end{tabular}   
Note that one can construct diverse variants of other kinds of problems as well, following this model: it doesn't have to be a minimization problem, nor does the solution have to be a subset of some kind. Indeed, the example about floor plans described above has neither of these properties. What is relevant is that one should have (i) some notion of \"good quality\" solutions (for \(X\), this equates to a small size) and (ii) some notion of a set of solutions being \"diverse\". **Diversity measures. ** The concept of diversity appears also in other fields, and there are many different ways to measure the diversity of a collection. For example, in ecology, the diversity of a set of species (\"biodiversity\") is a topic that has become increasingly important in recent times--see, for example, [PERSON] and [PERSON] [12]. Another possible viewpoint, in the context of multicriteria optimization, is to require that the sample of solutions should try to represent the _whole solution space_. This concept can be quantified for example by the geometric _volume_ of the represented space [13; 14], or by the _discrepancy_[15]. See ([16], Section 3) for an overview of diversity measures in multicriteria optimization. In this paper, we follow the simple possibility of looking for a collection of good solutions that have large _distances_ from each other, in a sense that will be made precise below, see Equations (1)-(2). Direction (2), i.e., taking the pairwise sum of all Hamming distances, has been taken by many practical papers in the area of genetic algorithms--see, e.g., [17; 18]. This now classical approach can be traced as far back as 1992 [19]. In [20], it has been boldly stated that this measure (and its variations) is one of the most broadly used measures in describing population diversity within genetic algorithms. One of its advantages is that it can be computed very easily and efficiently unlike many other measures, e.g., some geometry or discrepancy based measures.