3
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Dec 31 '18 at 1:54
  • $\begingroup$ @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$? $\endgroup$ – Tomer Aberbach Dec 31 '18 at 1:59
  • 1
    $\begingroup$ Sorry, I forgot to explain. Indeed, the elements in the sets in $A$. So here the base set would be $\{1,2,3,4\}$. $\endgroup$ – Hendrik Jan Dec 31 '18 at 2:02
  • $\begingroup$ 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\}$ $\endgroup$ – Hendrik Jan Dec 31 '18 at 2:14
  • $\begingroup$ @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. $\endgroup$ – Tomer Aberbach Dec 31 '18 at 2:18
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tomer Aberbach Dec 31 '18 at 21:53
  • $\begingroup$ 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$). $\endgroup$ – xskxzr Jan 1 at 4:24
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.