2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\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$ – Samuel Pilz Sep 5 '18 at 14:19
  • $\begingroup$ You are right. It should be ordinal number j. I edited my answer. $\endgroup$ – user3563894 Sep 5 '18 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$ – Samuel Pilz Sep 5 '18 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$ – user3563894 Sep 5 '18 at 14:34

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.