Given a large collection $\mathcal{X} = \{X_1, X_2, \dots, X_n\}$, where each $X_i$ is a set of integers, what's a fast algorithm to identify all pairs $(i,j)$ with $i \ne j$ such that $X_i \subseteq X_j$?

The best I can think of is the following (rather naive) algorithm:

  • Sort each set $X_i$.
  • Sort $\mathcal{X}$ by cardinality (smallest to largest). Tag each set with its original position in $\mathcal{X}$.
  • For each pair $1 \le i < j \le n$, check if $X_i \subseteq X_j$. Since $X_i$ and $X_j$ are sorted, this can be done with a single linear pass, similar to the merging step of merge sort. If so, output the original positions of $X_i$ and $X_j$.

This takes $O(n^2m + nm\log m)$ time, where $m = \max_i|X_i|$.

I suspect it's possible to obtain some improvement, since by transitivity, not all $n(n-1)/2$ pairwise comparisons are always necessary. If it has been determined that $X_i \subseteq X_j$ and $X_j \subseteq X_k$, then $X_i \subseteq X_k$ is known with no additional work. Similarly, if $X_i \not\subseteq X_k$ and $X_i \subseteq X_j$, then $X_j \not\subseteq X_k$. However, to take advantage of this, I need a fast way to notice that transitivity (or a transitivity violation) has occurred.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.