# FPT Algorithms for Diverse Collections of Hitting Sets
## Preliminaries  
Given two integers \(p\) and \(q\), we denote by \([p,q]\) the set of all integers \(r\) such that \(p\leq r\leq q\) holds. Given a graph \(G\), we denote by \(V(G)\) (resp. \(E(G)\)) the set of _vertices_ (resp. _edges_) of \(G\). For a subset \(S\subset V(G)\), we use \(G[S]\) to denote the subgraph of \(G\) induced by \(S\), and \(G\setminus S\) for the graph \(G[V(G)\setminus S]\). A set \(S\subseteq V(G)\) is a vertex cover (resp. a feedback vertex set) if \(G\setminus S\) has no edge (resp. no cycle). Given a graph \(G\) and a vertex \(v\) such that \(v\) has exactly two neighbors, say \(w\) and \(w^{\prime}\), _contracting_\(v\) consists of removing the edges \(\{v,w\}\) and \(\{v,w^{\prime}\}\), removing \(v\), and adding the edge \(\{w,w^{\prime}\}\). Given a graph \(G\) and a vertex \(v\in V(G)\), we denote by \(\delta_{G}(v)\) the _degree_ of \(v\) in \(G\). For two vertices \(u,v\) in a connected graph \(G\), we use \(\operatorname{dist_{T}}(u,v)\) to denote the _distance_ between \(u\) and \(v\) in \(G\), which is the length of a shortest path in \(G\) between \(u\) and \(v\).  
A _deepest leaf_ in a tree \(T\) is a vertex \(v\in V(T)\) such that there exists a root \(r\in V(T)\) satisfying \(\operatorname{dist_{T}}(r,v)=\max_{u\in V(T)}\operatorname{dist_{T}}(r,u)\). A _deepest leaf_ in a forest \(F\) is a deepest leaf in some connected component of \(F\). A deepest leaf \(v\) has the property that there is another leaf in the tree at distance at most 2 from \(v\) unless \(v\) is an isolated vertex or \(v\)'s neighbor has degree 2.  
The objective function \(\operatorname{div_{total}}\) in (2) has an alternative representation in terms of frequencies of occurrence [21]: If \(y_{v}\) is the number of sets of \(\{S_{1},\ldots,S_{r}\}\) in which \(v\) appears, then  
\[\operatorname{div_{total}}(S_{1},\ldots,S_{r})=\sum_{v\in U}y_{v}(r-y_{v}). \tag{3}\]  
**Auxiliary problems.** We define two auxiliary problems that we will use in some of the algorithms presented in Section 3. In the Maximum Cost Flow problem, we are given a directed graph \(G\), a _target_\(d\in\mathbb{R}^{+}\), a _source vertex_\(s\in V(G)\), a _sink vertex_\(t\in V(G)\), and for each edge \((u,v)\in E(G)\), a _capacity_\(c(u,v)>0\), and a _cost_\(a(u,v)\). A \((s,t)\)_-flow_, or simply _flow_ in \(G\) is a function \(f\colon E(G)\to\mathbb{R}\), such that for each \((u,v)\in E(G)\), \(f(u,v)\leq c(u,v)\), and for each vertex \(v\in V(G)\setminus\{s,t\}\), \(\sum_{(u,v)\in E(G)}f(u,v)=\sum_{(v,u)\in E(G)}f(v,u)\). The _value_ of the flow \(f\) is \(\sum_{(s,u)\in E(G)}f(s,u)\) and the _cost_ of \(f\) is \(\sum_{(u,v)\in E(G)}f(u,v)\cdot a(u,v)\). The objective of the Maximum Cost Flow problem is to find the maximum cost \((s,t)\)-flow of value \(d\).  
The second problem is the Maximum Weight \(b\)-Matching problem. Here, we are given an undirected edge-weighted graph \(G\), and for each vertex \(v\in V(G)\), a _supply_\(b(v)\). The goal is to find a set of edges \(M\subseteq E(G)\) of maximum total weight such that each vertex \(v\in V(G)\) is incident with at most \(b(v)\) edges in \(M\).