# Is selecting some of the sets such that their intersection is of size k NP-hard?

Given collection of sets S1,...,Sn and a positive number k. Is the problem of selecting some of the sets such that their intersection is of size k NP-hard?

So far, I tend to believe it is so I tried to find a reduction (unsuccessful so far), I have tried is to replace intersection by union (which is equivalent if we take the complementary sets).

I've also tried to dualize the problem and view a values as representing sets where they appear (unfortunately this transformed problem is not equivalent Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones)

I don't know if this problem is of interest for the reduction but it is the closest hard one I've found http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf

• Equivalently: given sets $T_1,\dots,T_n$ and a positive number $k'$, select some of the sets so that their union is of size $k'$. (The equivalence is obtained by taking $T_i = \overline{S_i}$ and $k'=m-k$, where $m$ is the number of elements in the universe, i.e., the cardinality of $S_1 \cup \dots \cup S_n$.)
– D.W.
Commented Feb 19, 2017 at 20:41

As you suggested, the problem is equivalent to selecting sets with union of given size $k$. It is not easier than selecting given numbers (say, $m$) of sets with union of given size $k$, since we could add different auxiliary elements $a_S^{(0)},\ldots,a_S^{(n)}$ to each set $S$ and ask for a union of size $m(n+1)+k$, where $n$ is the size of the original universe. Now it is not hard to show the later problem is NP-hard because of a reduction from X3C (exact cover by 3-sets).

• Unfortunately I don't see how the reduction would work because in my problem I don't have the restriction "every element of X occurs in exactly one member of C’ "? In my problem you could well select all the sets to cover the universe. Commented Feb 19, 2017 at 18:10
• @user3020699 Suppose in X3C the size of the universe is $n=3q$, then it's the same as selecting $q$ 3-sets with union of size $n$. Commented Feb 20, 2017 at 2:06
• but my problem does not constraint the number of sets to select, it only constraints k = the size of the union. So if you ask to cover the universe {1,...,n}, my problem can select all the sets as a solution. Commented Feb 20, 2017 at 6:37
• @user3020699 That's exactly what my answer tried to tell. Commented Feb 20, 2017 at 6:46
• So you agree that the reduction does not work (you can't solve X3C using my problem because the selected do not guarantee "every element of universe occurs in exactly one member of selected sets") or do you maintain it works and I missed your point? Commented Feb 20, 2017 at 9:38