1
$\begingroup$

select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

$\endgroup$
1
$\begingroup$

Your problem can be solved in polynomial time. Form an undirected graph where each set is a vertex, and there is an edge between two sets if they have a non-empty intersection. Decompose it into connected components, and let the sizes of the connected components be $n_1,\dots,n_t$. Then there exists a solution to your problem if and only if there is a subset of the integers $n_1,\dots,n_t$ that sums to $k$. This is the unary subset-sum problem, and it has a polynomial-time algorithm (via dynamic programming). Consequently, your problem can be solved in polynomial time, too.

In contrast, set packing (does there exist a way to select k sets so that each selected set has an empty intersection with all the other selected ones?) is NP-hard.

$\endgroup$
  • $\begingroup$ Thank you for this elegant algorithm. Unfortunately I think I made a mistake and my dual problem is not equivalent. I'm curious to know if a polynomial time Algol also exists for that one: Given collection of sets S1,...,Sn and a positive number k. Select some of the sets such that their intersection is of size k. Thanks $\endgroup$ – user3020699 Feb 18 '17 at 20:12
  • $\begingroup$ @user3020699, I suggest you post a new question asking about that one. Do make sure to think hard about it first before asking, and tell us in the question what approaches you've tried (what algorithm designs have you tried? have you tried showing it is NP-complete? what problems have you tried reducing from?) $\endgroup$ – D.W. Feb 19 '17 at 5:09
  • $\begingroup$ Thank you (I edited this question to only keep the original problem only). Here is the other questions link cs.stackexchange.com/questions/70500/… $\endgroup$ – user3020699 Feb 19 '17 at 6:55

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.