2
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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$.) $\endgroup$
    – D.W. ♦
    Commented Feb 19, 2017 at 20:41

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – user3020699
    Commented Feb 19, 2017 at 18:10
  • $\begingroup$ @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$. $\endgroup$
    – Wei Zhan
    Commented Feb 20, 2017 at 2:06
  • $\begingroup$ 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. $\endgroup$
    – user3020699
    Commented Feb 20, 2017 at 6:37
  • $\begingroup$ @user3020699 That's exactly what my answer tried to tell. $\endgroup$
    – Wei Zhan
    Commented Feb 20, 2017 at 6:46
  • $\begingroup$ 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? $\endgroup$
    – user3020699
    Commented Feb 20, 2017 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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