# Find 2 sets with an empty intersection

I have the following problem. The problem can be formulated in three different ways

Given sets $$B_{-n},\ldots,B_n \subset \{1,\ldots,m\}$$.

Find $$i,j \in \{-n,\ldots,n\}$$ with $$|i| \neq |j|$$ and $$i,j \neq 0$$ that satisfy $$B_i \cap B_j = \emptyset$$

"Invert" the sets $$B_i$$

Define $$A_k=\{i: k\in B_i \}$$. $$A_1, \ldots, A_m \subset \{-n,\ldots,n\}$$.

Find $$i,j \in \{-n,\ldots,n\}$$ with $$|i| \neq |j|$$ and $$i,j \neq 0$$ that satisfy the property $$\{i,j\} \not\subset A_k$$ for all $$k=1,\ldots,m$$

Relation instead of set of sets

Define relation $$R\subset\{1,\ldots,m\}\times\{-n,\ldots,n\}$$ with $$kRi \equiv k \in B_i$$.

Find $$i,j \in \{-n,\ldots,n\}$$ with $$|i| \neq |j|$$ and $$i,j \neq 0$$ that satisfy the property for no $$k=1,\ldots,m: kRi \land kRj$$

Naive Algorithm

As far as I can tell, the 3 problems are the same thing viewed from slightly different perspectives. One possible algorithm would be to iterate through all pairs $$(i,j)$$ and check if the condition is satisfied. This algorithm has runtime of $$\mathcal{O}(n^2\cdot f(m,n))$$ with the runtime $$f$$ of the check if the pair satisfies the property.

Specifically for the first case: Assuming the sets are implemented sorted lists the intersection can be checked to be empty in $$\mathcal{O}(m)$$ time via a simple mergesort-like scan.

Question

Is there an algorithm for this problem that solves it in $$\mathcal{o}(n^2)$$ time? (maybe with some tradeoff in the $$m$$ component)

Here is one example for an algorithm, which can run at $$O(4^m \cdot m+ n\cdot m)$$ time, which is $$o(n^2)$$ if $$m\ll c\log n$$ for every $$c<0.5$$.
We convert a subset $$B_i$$ into an ordinal number $$1\leq j\leq 2^m$$, a number of $$m$$-bits, in $$O(m)$$ time, where the $$k^{\text{th}}$$ bit of $$j$$ euqals one iff $$k\in B_i$$. Now, for every ordinal number $$j$$ we save a link list $$L_j$$ which contains pointers to all subsets $$B_i$$ that are associated with ordinal number $$j$$. This can be done in $$O(n\cdot m)$$ time.
Second, since all subsets with the same ordinal number are containing the same elements, using $$O(m)$$ time we can determine for every ordinal numbers $$j_1,j_2$$ if the corresponding subsets of $$L_{j_1},L_{j_2}$$ have a common element (i.e., there exists $$1\leq k\leq m$$ s.t., the $$k^{\text{th}}$$ bit of both $$j_1$$ and $$j_2$$ is one) or not. In case the corresponding subsets have empty intersection, and in case that $$L_{j_1}$$ and $$L_{j_2}$$ are non empty, and it is NOT the case where $$L_{j_1},L_{j_2}$$ containing a single subset, pointing respectively to to $$B_{n}$$ and $$B_{-n}$$, then we can find $$B_{i}$$ and $$B_{j}$$ satisfying the above condition in $$O(1)$$.
In the worst case, we run over all ordinal numbers $$1\leq j_1,j_2\leq m$$ in $$O((2^m)^2)=O(4^m)$$ time, and checking an empty intersection takes $$O(m)$$ time. Since the first step takes $$O(n\cdot m)$$ time, the complexity of the algorithm is $$O(4^m \cdot m+ n\cdot m)$$.
• I have some trouble understanding your approach. The list $L_j$ contains pointers to subsets $B_i$ that have ordinal number $i$? What is the difference between $i$ and $j$ in this sentence? – Samuel Pilz Sep 5 '18 at 14:19
• In that case, I still do not get the algorithm. The list $L_j$ only contains identical sets because the bit-string interpretation identifies the subset. How can $L_{j_1}$ and $L_{j_2}$ have a common element? – Samuel Pilz Sep 5 '18 at 14:32
• If the $k^{th}$ bit of $j_1$ and $j_2$ equals to $1$, then $k$ is a common element of every subset in $L_{j_1}$ and $L_{j_2}$. – user3563894 Sep 5 '18 at 14:34