Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Welcome! Is the base set finite? –  Raphael Aug 6 '12 at 5:17
1  
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 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.