Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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^1$ is defined similarly as the union of the following six sets:
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.
