Given $A = [[4, 10, 14], [5, 13, 14], [2, 7, 13], [0, 2, 12], [2, 4, 11], [3, 5, 11], [3, 7, 10], [6, 9, 10], [0, 1, 3]]$ is a list of sets. I want to find the maximum number of sets from the list which are disjoint. (By disjoint, I mean that if I have selected $[4,10,14]$ then I cannot select $[5,13,14]$ since it contains $14$ which I had already chosen in the previous set.
The answer for this particular problem would be 4, as I can choose $[0,1,3], [6, 9, 10],[2, 4, 11],[5, 13, 14]$
I tried the greedy approach but it does not seem to be optimal for all cases. Any suggestions on what algorithms/approaches I can try out ?
Best Answer
This Maximum Disjoint Set problem is NP-complete.
This was shown at CS.SE.