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$

Question

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:

1. Let $B = \emptyset$ initially.
2. Let $S$ be the set of set(s) of lowest of cardinality in $A$.
3. Let $I$ be the intersection of the sets in $S$.

4. 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$.

5. 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?

Answer 1

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\}\}$.

Answer 2

This problem sounds very interesting. I am not aware of any name for this problem, however.

Your algorithm is not correct.

Here is a counterexample. $A = \{ \{ 1, 2 \}, \{ 1, 3 \}, \{1, 4\}, \{2,3\}, \{2,4\}\}$. The minimal set of pairwise disjoint sets such that each set in A can be expressed as a union of sets in it is $B = \{ \{1\}, \{2 \}, \{ 3 \}, \{ 4 \} \}$, which has 4 elements. However, in the step 4 of your algorithm, all 5 sets in $A$ will be added.

In fact, as you pointed out, the step 4 may add non-disjoint sets, thus invalidating the algorithm. The smallest counterexample is $A = \{\{1, 2 \}, \{2, 3 \}, \{1,3\}\}$. The step 4 of the algorithm will add all 3 sets in $A$, which contains no disjoint pairs.

Answer 3

The problem posed is the “minimum disjoint set basis” for a family of sets (A in this case); see “Finding Augmented-Set bases,” by V. Gligor and D. Maier in SIAM Journal on Computing, bol. 11, no. 3, Aug 1982. The solution can be found in O(mn)time as mentioned