# 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. Feb 19 '17 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).
• @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$. – Willard Zhan Feb 20 '17 at 2:06