7
$\begingroup$

Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.

Lets assume that $m$ is less than some polynomial in $n$, i.e.: $m < P(n)$. In this case is there an efficient (polynomial) algorithm for the optimization problem:

Find the smallest set which contains at least $k$ of the $n$ given sets.

$\endgroup$
  • $\begingroup$ Do you have any relation between n and m? I mean is it correct to assume n<=m? $\endgroup$ – user742 Aug 26 '12 at 13:51
  • $\begingroup$ Dominating set for Bipartite graphs is NP-Hard. This might apply. $\endgroup$ – Aryabhata Aug 27 '12 at 6:52
8
$\begingroup$

The problem is NP-complete. Here is a reduction from 3SAT-5, an NP-complete version of 3SAT in which every variable appears exactly 5 times (and so the number of variables and number of clauses are linearly related).

We start by constructing two set systems. The first system $\mathcal{S}$ consists of 6 sets $A_0,A_1,B_0,B_1,C_0,C_1$ and 15 elements $D = \{0,1\}^4 \setminus (1,1,1,1)$, and has the following property: $$ |A_i \cup B_j \cup C_k| = \begin{cases} 14 & \text{if } i=j=k=0, \\ 13 & \text{otherwise}. \end{cases} $$ The set system is given by $$\begin{align*} A_i &= \{(a,b,c,d) \in D : a = i\}, \\ B_i &= \{(a,b,c,d) \in D : b = i\}, \\ C_i &= \{(a,b,c,d) \in D : c = i\}. \end{align*}$$ The only elements not covered by $A_i \cup B_j \cup C_k$ are those of the form $(1-i,1-j,1-k,d)$. If $i = j = k = 0$ then there is one such element, otherwise there are two.

The second system $\mathcal{T}$ consists of $2n$ sets $X_1,Y_1,\ldots,X_n,Y_n$ and $O(n^2)$ elements, and has the following property. Call a family of $n$ sets out of $\mathcal{T}$ proper if it contains exactly one of each $X_i,Y_i$. All proper families of $n$ sets cover the same number of elements $M$, and each improper family of $n$ sets covers at least $M+1$ elements.

The set of elements consists of all unordered pairs of sets $\{S,T\}$ other than those of the form $\{X_i,Y_i\}$. Each set $S \in \mathcal{T}$ consists of all $2n-2$ pairs containing it. Let $\mathcal{F}$ be a family of $n$ sets, with complement $\overline{\mathcal{F}}$. The only elements not covered by $\mathcal{F}$ are those of the form $\{S,T\}$ where $S,T \in \overline{\mathcal{F}}$. If $\mathcal{F}$ is proper then so is $\overline{\mathcal{F}}$, and so there are $\binom{n}{2}$ elements not covered. If $\mathcal{F}$ is improper then so is $\overline{\mathcal{F}}$, and so there are fewer than $\binom{n}{2}$ elements not covered.

The reduction. Let $\phi$ be an instance of 3SAT-5 with $n$ variables and $m=5n/3$ clauses. For each clause $\phi_j$ there is a copy $\mathcal{S}_j$ of system $\mathcal{S}$. There is also a copy $\tilde{\mathcal{T}}$ of $\mathcal{T}$ in which each element is replaced by $N = 13m+1$ elements. The total number of elements is polynomial in $n$.

For each variable $x_i$ there are two sets $X_i^0$ and $X_i^1$. The set $X_i^0$ is the union of the following six sets:

  • the set $X_i$ of $\tilde{\mathcal{T}}$
  • for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears positively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
  • for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
  • for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The set $X_i^1$ is defined similarly as the union of the following six sets:

  • the set $Y_i$ of $\tilde{\mathcal{T}}$
  • for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears negatively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
  • for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
  • for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The problem is to decide whether there are $n$ sets which together cover $13m+NM$ elements (or less).

If $\phi$ is satisfiable, say with truth assignment $x_i$, then $\{X_i^{x_i} : 1 \leq i \leq n\}$ covers exactly $13m+NM$ elements. Conversely, suppose there is a way to cover at most $13m+NM$ elements. If the solution is improper then it covers at least $N(M+1) > 13m+NM$ elements (considering only $\tilde{\mathcal{T}}$). If it is proper then it corresponds to some truth assignment $x_i$, and it is easy to check that the number of elements covered is $13m+NM+Z$, where $Z$ is the number of falsified clauses. Hence $Z = 0$ and we conclude that $x_i$ is a satisfying assignment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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