2
$\begingroup$

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.

$\endgroup$

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.