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:

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?
• Call two elements in the base set equivalent if they belong to the same sets from $A$. Now your sets $B$ are the equivalence classes. This of course is not an algorithm, but it might help solving the problem. Dec 31, 2018 at 1:54
• @HendrikJan When you say "two elements in the base set" is "elements" referring to sets in the base set $A$ or elements in the sets in $A$? Dec 31, 2018 at 1:59
• Sorry, I forgot to explain. Indeed, the elements in the sets in $A$. So here the base set would be $\{1,2,3,4\}$. Dec 31, 2018 at 2:02
• You start with smallest sets. Start however with the full set and split. Begin with $\{1,2,3,4\}$. First set in $A$ shows we get $\{1,2\},\{3,4\}$. Second set needs another split $\{1,2\},\{3\},\{4\}$ Dec 31, 2018 at 2:14
• @HendrikJan I'm not sure I fully understand how you decide where to split, but if you could post an answer explaining further that would be great. Dec 31, 2018 at 2:18

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

• Would you be able to clarify what you mean by "components" in the context of Venn diagrams? I am not familiar with what qualifies as a "component" in a Venn diagram. Additionally, do you have any intuition you could share with me to help me understand why the algorithm works? Dec 31, 2018 at 21:53
• For $n$ sets $A_1,\ldots,A_n$, each component can be expressed as $X_1\cap \cdots\cap X_n$ where $X_i$ is either $A_i$ or $\bar{A}_i$. There are $2^n-1$ components ($\bar{A}_1\cap \cdots\cap \bar{A}_n$ is always empty since the universe is $A_1\cup \cdots\cup A_n$). Jan 1, 2019 at 4:24

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.

• Well looks like it's back to the drawing board... An even simpler counterexample would be $A = \{ \{ 1, 2 \}, \{ 2, 3 \}, \{ 3, 4 \} \}$. Dec 31, 2018 at 1:50