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.


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


1 Answer 1


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

  • $\begingroup$ 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? $\endgroup$ Commented Sep 5, 2018 at 14:19
  • $\begingroup$ You are right. It should be ordinal number j. I edited my answer. $\endgroup$ Commented Sep 5, 2018 at 14:21
  • $\begingroup$ 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? $\endgroup$ Commented Sep 5, 2018 at 14:32
  • $\begingroup$ 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}$. $\endgroup$ Commented Sep 5, 2018 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.