Efficiently finding the intersections of sets that yield a desired set

Question

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.

Answer 1

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.