select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones
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
np complete
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.