On Mon, Apr 08, 2013 at 11:11:40AM -0400, Stavros Macrakis wrote:
> Given a set of sets S, what is the minimal set of disjoint sets D such that
> each of the original sets is a union of elements of D?
>
> For example, if S = { {a,b,c,d,e}, {a,c}, {c,f,g} }, then D = { {a}, {c},
> {f, g}, {b,d,e} }.
>
> What is the name of this problem?
>
> The obvious way to solve it is to calculate the full lattice of
> intersections and set differences, but the straightforward way of doing
> that seems computationally expensive. What are good algorithms for this
> problem?
>
Without the disjointness condition it would be the "set basis problem"
http://en.wikipedia.org/wiki/Bipartite_dimension
However with the disjointness condition it has an easy algorithm:
consider the equivalence relation ~ between elements x, y of the universe:
x ~ y if x and y occur precisely in the same sets of S.
Now the partitioning of the universe corresponding to ~ (i.e., the
equivalence classes) is the optimal D.
Oliver