3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – nir shahar
    Mar 15 at 22:59

1 Answer 1

1
$\begingroup$

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$.
$\endgroup$
9
  • $\begingroup$ @JohnL., oh, right! Thank you. Fixed. $\endgroup$
    – D.W.
    Mar 17 at 3:32
  • $\begingroup$ 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). $\endgroup$
    – John L.
    Mar 17 at 3:44
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Mar 17 at 4:19
  • $\begingroup$ Changing a collection such as a set or a list while looping over it is apparently ambiguous. $\endgroup$
    – John L.
    Mar 17 at 5:02
  • $\begingroup$ @JohnL., "pop" means pick a single element of $W$ (any one is fine) and remove it. It doesn't mean looping over it. $\endgroup$
    – D.W.
    Mar 17 at 5:19

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.