Maximal disjoint subset problem

[mXSCNT]

We have a set of sets S = {s1, s2, ..., sn}. We seek a maximal subset of S, such that the sets in that subset are all pairwise disjoint.

How difficult is this? Is it NP-complete? Does this problem have a name?

 

[junglebeast]

I don't think that this problem has a name. It may be possible to formulate this as a dynamic programming problem, think about that a little if you will.

 

[mXSCNT]

Oh, I just realized it is the max clique problem... for a given graph G = (V,E), assign each node a set s(n). Let s(n) = {(n,b) | b != n and the edge (n,b) is not in the graph}. That implies there is an edge between two nodes a,b if and only if s(a) and s(b) are pairwise disjoint. So the maximum size pairwise disjoint subset of S = {s(n) | n is in V} consists of the sets corresponding to nodes in the max clique of the graph. This reduction is polynomial time, so my maximal disjoint subset problem is NP-complete.