Given n sets of integers, how to maximize the number of non overlapping sets

Question

Given n sets of integers, how to maximize the number of non overlapping sets?

For example, lets the given sets be,

{1,2,3}
{1,4,5}
{6,7,8}
{2,3}
{8,9}
{9}

Then the answer will be 4,

 {1,4,5}, {6,7,8}, {2,3}, {9}

{1,2,3} and {1,4,5} can not consist of the non overlapping sets because 1 is common in both sets. Is it an NP heard problem? I will expect a little detail if there is an efficient solution for that problem.

[N.B.] The number of input sets can be upto 1000 with each set containing upto 1000 integers.

Answer 1

That's a Maximum Independent Set problem, where your sets correspond to nodes, and nodes corresponding to sets that share at least one element have an edge between them. It's NP-Hard and also hard to approximate to a constant factor.

You can still attempt to solve it, for example with integer linear programming:

maximize: sum x[i]

for each pair of sets (i,j) that overlap: x[i] + x[j] <= 1

x[i] is a boolean indicated whether the i'th set is part of the MIS that you're finding.