Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in $O(|A| \cdot |B| \cdot |U|)$, is there way to improve this?

Say, $|U| \leq 32$. Is there a way to speed algorithm up?

If it matters, one can assume, that all elements in $A \cup B$ are unique. Another variation of the problem is $A \equiv B$ and there is a need to search $a$ and $b$ from the single set.

  • $\begingroup$ if $|U|\le 32$ then $|A|,|B|\le 2^{32}$ and therefore the algorithm would be constant-time. I suppose this is not really an interesting case for you $\endgroup$ – nir shahar Jul 9 '20 at 12:47
  • $\begingroup$ Oh and what data structure do you use to keep track of $A,B,U$? $\endgroup$ – nir shahar Jul 9 '20 at 12:48
  • $\begingroup$ However the number of subsets of $|U|$ is limited if $|U|$ is, and therefore also $|A|,|B|$ $\endgroup$ – nir shahar Jul 9 '20 at 13:41
  • $\begingroup$ $A$ and $B$ are sets of sets. Values of $|A|$ and $|B|$ capped by $2^{|U|}$. For elements of $A$, $B$ I use bitmasks of size $|U|$. For $U$ -- does not matter. $\endgroup$ – Tomilov Anatoliy Jul 9 '20 at 13:42
  • $\begingroup$ What im saying is that if $|U|$ is capped, then also the size of $A$ and $B$. Thus the time would be constant (as its capped by a constant) $\endgroup$ – nir shahar Jul 9 '20 at 13:43

Set $A = B$ and $|U| = \Theta(\log |A|)$, and you run up against the Orthogonal Vectors Conjecture trying to do better than $|A|^{2-o(1)}$.


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.