# 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 '12 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. – Nicholas Mancuso Aug 10 '12 at 18:15

## 1 Answer

The problem is NP-complete. This rules out an exact algorithm that works in all circumstances, but does not rule out heuristic algorithms that work well in practice, or approximations algorithm with provable approximation guarantees.

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.