2
$\begingroup$

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.

$\endgroup$
7
  • $\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, 2020 at 12:47
  • $\begingroup$ Oh and what data structure do you use to keep track of $A,B,U$? $\endgroup$
    – nir shahar
    Jul 9, 2020 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, 2020 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$ Jul 9, 2020 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, 2020 at 13:43

1 Answer 1

1
$\begingroup$

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)}$.

$\endgroup$

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.