# Problem similar to set packing

Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse set $S$ in a family of sets $\mathcal{F}$?

One approach is to solve a modified set packing problem. Suppose $\mathcal{F}=\{S_1,\dotsc,S_k\}$. Let $K$ be a subset of elements, $K \subset \bigcup S_i$, and let $\mathcal{F}_{-K}=\{S_1 \setminus K,\dotsc, S_k \setminus K\}$. Then the maximal diverse set $S$ corresponds to the largest maximal set packing obtained from $\mathcal{F}_{-L}$ where $L$ is the set of all non-unique elements in $\mathcal{F}$.

But, what's a good heuristic for choosing $K$? Or are there better approaches altogether?

• Welcome! Is the base set finite?
– Raphael
Aug 6, 2012 at 5:17
• Notice that you are asking for a minimal set $S$ such that the resulting $\mathcal{F}_{-S}$ is an anti-chain under the subset relation. Aug 10, 2012 at 18:15

The reduction is from 3SAT. Given a 3SAT instance $\phi$ with variables $x_1,\ldots,x_n$ and clauses $\phi_1,\ldots,\phi_m$, construct the following set system. For each variable $x_i$ there are two sets $A_{i,0}$ and $A_{i,1}$ and $N=n+1$ sets $B_{i,t} = \{\beta_{i,t,0},\beta_{i,t,1}\}$, and for each clause $\phi_j$ there is a set $C_j = \{\gamma_{j,1},\gamma_{j,2},\gamma_{j,3}\}$. The set $A_{i,b}$ consists of the following elements:
• The $N+1$ elements $\alpha_i,\beta_{i,1,b},\ldots,\beta_{i,N,b}$.
• For each clause $\phi_j$ that contains $x_i$ as the $k$th literal and is not satisfied by $x_i = b$, the element $\gamma_{j,k}$.
One can find $n(N+1)+m$ diverse sets if and only if $\phi$ is satisfiable. Indeed, given a satisfying assignment $\vec{x}$, the family $\{ A_i^{x_i} : i \in [n] \} \cup \{ B_{i,t} : i \in [n], t \in [N] \} \cup \{ C_j : j \in [m] \}$ is diverse: $\alpha_i$ belongs only to $A_i^{x_i}$, $\beta_{i,t,1-x_i}$ belongs only to $B_{i,t}$, and if the $k$th literal of $\phi_j$ is satisfied then $\gamma_{j,k}$ belongs only to $C_j$.
For the converse, suppose $\mathcal{S} = \mathcal{A} \cup \mathcal{B} \cup \mathcal{C}$ is a diverse family of size at least $n(N+1)+m$, partitioned according to the type of the set. If $\mathcal{A}$ contains both $A_{i,0}$ and $A_{i,1}$ for some $i$, then $B_{i,1},\ldots,B_{i,N} \notin \mathcal{B}$. Hence $|\mathcal{S}| \leq 2n + (n-1)N + m < n(N+1) + m$, which is impossible. Therefore $\mathcal{B}$ and $\mathcal{C}$ must contain all sets of the corresponding type, and $\mathcal{A}$ must contain $n$ sets, which together encode an assignment $\vec{x}$. Since $C_j \in \mathcal{S}$ is diverse, by construction the assignment $\vec{x}$ satisfies clause $\phi_j$, hence $\phi$ is satisfiable.