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

Question

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?

Answer 1

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