# Fast algorithm for computing minimal closure of a set of sets under intersection?

A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $$S$$) under intersection", I mean:

Given a set $$S$$ containing sets $$s_1, \cdots , s_k$$, the smallest set $$𝑆′$$ such that $$S\subseteq S'$$ and $$x\cap y \in S'$$ for any two sets $$x, y \in S'$$.

While I can come up with a pretty straightforward naive approach (loop over the sets and store all the intersections in a new set, then update the set as the union of previous step’s set and the new set, and repeat this process until the new and old set are the same), I am looking for a faster method, but haven’t been able to find any papers working on a similar problem. Does anybody know if there are faster existing algorithms to solve this problem before I attempt to potentially reinvent the — or a worse version of — the wheel? Or if not exact solutions, maybe fast approximation algorithms on other data structures (e.g. sets of strings) that translate to this problem setup?

• The result will literally be the set $S'$ containing all sets $s'$ of the form $s'=\bigcap s\in A$ for some $A\subseteq S'$. Since the output can be incredibely large, (up to an exponantial size in the input) - there is no "fast" algorithm for this problem. Mar 15 at 22:59

There is no polynomial-time algorithm. The output can potentially be exponentially large, so any algorithm will have inputs on which it must take exponential time. For instance, if $$s_i=\{1,2,\cdots, k\}\setminus\{i\}$$, then $$S'$$ contains $$2^k$$ elements, so any algorithm must take $$\Omega(2^k)$$ time (it takes that much time even just to output $$S'$$, let alone to calculate it).

One simple approach is a workload algorithm, where you incrementally generate new sets that are in the closure. In particular:

• Set $$W := S$$. (The worklist is initialized to $$S$$.)

• Set $$S' := S$$.

• While $$W \ne \emptyset$$:

• Pop an element from $$W$$, call it $$s$$.
• Let $$T := \{s \cap s' \mid s' \in S', s \cap s' \notin S'\}$$.
• Set $$W := W \cup T$$ and $$S' := S' \cup T$$.
• @JohnL., oh, right! Thank you. Fixed.
– D.W.
Mar 17 at 3:32
• Here is a simpler and faster algorithm. Computes $C_i$, the minimal closure of $\{s_1, s_2,\cdots, s_i\}$ for $i=0,1,2,\cdots,k$. $C_0=\emptyset$. $C_{i+1}=C_i\cup\{s\cap s_{i+1}\mid s\in C_i\}$. Return $C_k$. This algorithm is optimal in the sense that in the worst case, each $s\cap s_{i+1}$ will always be a new set. (I do not want to write another answer). Mar 17 at 3:44
• @JohnL., Thank you for the simpler algorithm! In my algorithm, if $s=s'$, then $s \cap s' \in S'$, and nothing is added to $W$ -- so I don't understand why you say $W$ will never become empty.
– D.W.
Mar 17 at 4:19
• Changing a collection such as a set or a list while looping over it is apparently ambiguous. Mar 17 at 5:02
• @JohnL., "pop" means pick a single element of $W$ (any one is fine) and remove it. It doesn't mean looping over it.
– D.W.
Mar 17 at 5:19