# Efficiently finding the intersections of sets that yield a desired set

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.

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.