# Find two disjoint set

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.

• 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 – nir shahar Jul 9 '20 at 12:47
• Oh and what data structure do you use to keep track of $A,B,U$? – nir shahar Jul 9 '20 at 12:48
• However the number of subsets of $|U|$ is limited if $|U|$ is, and therefore also $|A|,|B|$ – nir shahar Jul 9 '20 at 13:41
• $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. – Tomilov Anatoliy Jul 9 '20 at 13:42
• 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) – 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)}$$.