# 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

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

## 1 Answer

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.

• 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 Feb 18, 2017 at 20:12
• @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?)
– D.W.
Feb 19, 2017 at 5:09
• Thank you (I edited this question to only keep the original problem only). Here is the other questions link cs.stackexchange.com/questions/70500/… Feb 19, 2017 at 6:55