Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Maximal disjoint subset problem

  1. Aug 23, 2009 #1
    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?
  2. jcsd
  3. Aug 23, 2009 #2
    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.
  4. Aug 23, 2009 #3
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook