Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$

I recently thought of the following problem:

Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.

For example, if $A = \{ \{ 1, 2 \}, \{ 1, 2, 3 \}, \{3, 4\}, \{4\} \}$ then $B = \{ \{ 1, 2 \}, \{ 3 \}, \{ 4 \} \}$.

I designed the following algorithm:

• Let $B = \emptyset$ initially.

• Let $S$ be the set of set(s) of lowest of cardinality in $A$.

• Let $I$ be the intersection of the sets in $S$.

-
If $I = \emptyset$: add the sets in $S$ to $B$, remove the elements in the sets in $S$ from the sets in $A$, and remove $\emptyset$ from $A$.

If $I \neq \emptyset$: add $I$ to $B$, remove the elements in $I$ from the sets in $A$, and remove $\emptyset$ from $A$.

• Repeat from step 2 until $A = \emptyset$.

My questions are:

• Does this problem have a name?

• Is this algorithm correct?

• What is the complexity of this algorithm?

• Is this algorithm optimal, and if not, what would be a better algorithm?

Essentially you are finding all non-empty components of the Venn diagram of the sets in $A$. So here is an algorithm:

B = empty set
for each set S in A:
    for each set T in B:
        remove T from B
        compute (S \cap T), (T \ S) and (S \ T) 
        if (S \cap T) is not empty, add (S \cap T) into B
        if (T \ S) is not empty, add (T \ S) into B
        S = S \ T
    if S is not empty, add S into B
return B

This algorithm runs in $O(nm)$ time where $n$ is the number of all elements involved, and $m$ is the number of sets in $A$.

For your example, initially $B$ is empty.

After dealing with $\{1,2\}$, $B=\{\{1,2\}\}$.

After dealing with $\{1,2,3\}$, $B=\{\{1,2\},\{3\}\}$.

After dealing with $\{3,4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.

After dealing with $\{4\}$, $B=\{\{1,2\},\{3\},\{4\}\}$.

StackExchange Computer Science Q#102195, answer score: 2