1
$\begingroup$

Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as an intersection between sets where $S_i\cap S_j\cap \dots \cap S_k = \{x\}$, such that removing any one of the sets in the intersection changes the result from the desired set $\{x\}$ to something else.

For example, for the collection of sets $\{A,B,C,D,E,F\}$, where:

$A = \{c,d,f,g,x\}$,

$B = \{c,d,g,p,t,x\}$,

$C = \{e,i,x,y\}$,

$D = \{a,i,o,p,q,w,x\}$,

$E = \{f,t,w,x\}$, and

$F = \{a,b,c,d,e\}$, then:

  • $A \cap B \cap E = \{x\}$ is a reduced intersection, because $A\cap B = \{c,d,g,x\}$, $A\cap E = \{f,x\}$, and $B\cap E = \{t,x\}$. Removing any of the sets $A$, $B$, or $E$ from the intersection $A \cap B \cap E$ yields a different result than the desired set $\{x\}$.
  • $C \cap D \cap E = \{x\}$ is NOT a reduced intersection, because $C\cap E = \{x\}$. Removing set $D$ from the intersection $C \cap D \cap E$ still yields the desired set $\{x\}$ as the result.

My question is: given a collection of sets, what is the most efficient algorithm to find all the reduced intersections between those sets that yield a desired set?

Note that it doesn't matter whether the desired set has only a single element in it or not. In this example, I just used a single element $x$ for simplicity.

$\endgroup$
0
$\begingroup$

Your problem is equivalent to enumerating all inclusion-minimal set covers, a problem addressed here.

Suppose that you're looking for all collections of sets whose intersection is some set $T$. All the relevant sets must contain $T$, so you can just consider all sets containing $T$, and remove $T$ from all of them. This reduces to the case $T = \emptyset$.

Now let $U$ be the union of all sets. The intersection of a collection of sets is empty iff the union of their complements is $U$. In other words, if you complement all sets, then you're interested in inclusion-minimal set covers.

$\endgroup$
1
  • $\begingroup$ Thank you for pointing this out. I hadn’t noticed that my problem was equivalent to enumerating all inclusion-minimal set covers. $\endgroup$ – mathTrials Apr 28 '20 at 14:00

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.