# FPT Algorithms for Diverse Collections of Hitting Sets
## 3 A Framework for Maximally Diverse Solutions
### Optimal Augmentation  
Given a universe \(U\) and a set \(\mathcal{S}\) of subsets of \(U\), the problem \(\mathtt{diverse}_{r,k}(\mathcal{S})\) consists of finding an \(r\)-tuple \((S_{1},\ldots,S_{r})\) that maximizes \(\operatorname{div}_{\text{total}}(S_{1},\ldots,S_{r})\), over all \(r\)-tuples \((S_{1},\ldots,S_{r})\) such that, for each \(i\in[1,r]\), \(|S_{i}|\leq k\), and there exists \(S\in\mathcal{S}\) such that \(S\subseteq S_{i}\subseteq U\). Theorem 3.1: _Let \(U\) be a finite universe, \(r\) and \(k\) be two integers, and \(\mathcal{S}\) be a set of \(s\) subsets of \(U\). \(\mathtt{diverse}_{r,k}(\mathcal{S})\) can be solved in time \(r^{2}s^{r}\cdot|U|^{O(1)}\)._  
Proof: The algorithm that proves Theorem 3.1 starts by enumerating all \(r\)-tuples \((S_{1},S_{2},\ldots,S_{r})\in\mathcal{S}^{r}\) of elements from \(\mathcal{S}\). For each of these \(s^{r}\)\(r\)-tuples, we try to augment each \(S_{i}\), using elements of \(U\), in such a way that the diversity \(d\) of the resulting tuple \((T_{1},\ldots,T_{r})\) is maximized and such that, for each \(i\in[1,r]\), \(S_{i}\subseteq T_{i}\subseteq U\) and \(|T_{i}|\leq k\). It is clear that this algorithm will find the solution to \(\mathtt{diverse}_{r,k}(\mathcal{S})\). We show how to model this problem as a maximum-cost network flow problem with piecewise linear concave costs. This problem can be solved in polynomial time. (See, for example, [23] for basic notions about network flows). Without loss of generality, let \(U=\{1,2,\ldots,n\}\). We use a variable \(0\leq x_{ij}\leq 1\) to decide whether element \(j\) of \(U\) should belong to set \(T_{i}\). In an optimal flow, these values are integral. Some of these variables are already fixed because \(T_{i}\) must contain \(S_{i}\):  
\[x_{ij}=1\text{ for }j\in S_{i}. \tag{4}\]  
The size of \(T_{i}\) must not exceed \(k\):  
\[\sum_{j=1}^{n}x_{ij}\leq k,\text{ for }i=1,\ldots,r. \tag{5}\]  
Finally, we can express the number \(y_{j}\) of sets \(T_{i}\) in which an element \(j\) occurs:  
\[y_{j}=\sum_{i=1}^{r}x_{ij},\text{ for }j=1,\ldots,n. \tag{6}\]  
These variables \(y_{j}\) are the variables in terms of which the objective function (3) is expressed:  
\[\text{maximize }\sum_{j=1}^{n}y_{j}(r-y_{j}). \tag{7}\]  
These constraints can be modeled by a network as shown in Figure 1. There are nodes \(T_{i}\) representing the sets \(T_{i}\) and a node \(V_{j}\) for each element \(j\in U\). In addition, there is a source \(s\) and a sink \(t\). The arcs emanating from \(s\) have capacity \(k\). Together with the flow conservation equations at the nodes \(T_{i}\), this models the constraints (5). Flow conservation at the nodes \(V_{j}\) gives rise to the flow variables \(y_{j}\) in the arcs leading to \(t\) according to (6). The arcs with fixed flow (4) could be eliminated from the network, but, for ease of notation, we leave them in the model. The only arcs that carry a cost are the arcs leading to \(t\), and the costs are given by the concave function (7). There is now a one-to-one correspondence between integral flows from \(s\) to \(t\) in the network and solutions \((T_{1},\ldots,T_{r})\), and the cost of the flow is equal to the diversity (2) or (3). We are thus looking for a flow of maximum cost. The _value_ of the flow (to total flow out of \(s\)) can be arbitrary. (It is equal to the sum of the sizes of the sets \(T_{i}\).) The concave arc costs (7) on the arcs leading to \(t\) can be modeled in a standard way by multiple arcs. Denote the concave cost function by \(f_{y}:=y(r-y)\), for \(y=0,1,\ldots,r\). Then, each arc \((V_{i},t)\) in the last layer is replaced by \(r\) parallel arcs of capacity 1 with costs \(f_{1}-f_{0}\), \(f_{2}-f_{1}\), \(\ldots,f_{r}-f_{r-1}\). This sequence of values \(f_{y}-f_{y-1}=r-2y+1\) is decreasing, starting out with positive values and ending with negative values.