Finding a pair of non-overlapping bit vectors

Question

I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists.

For example, if I give you $[00110, 01100, 11000]$ then the only solution is $\{00110, 11000\}$. Alternatively, the input $[111, 011, 110, 101]$ has no solution. And any list that contains the all-zero bitvector $000...0$ and another element $e$ has a trivial solution $\{e, 000...0\}$.

Here's a slightly harder example, with no solution (each row is a bit vector, the black squares are 1s and the white squares are 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □ 
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

How efficiently can two non-overlapping bitvectors be found, or be shown not to exist?

The naive algorithm, where you just compare every possible pair, is $O(n^2 k)$. Is it possible to do better?

Answer 1

Warmup: random bitvectors

As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random. Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$).

We'll consider the following two-set variant of the problem:

Given sets $S,T \subseteq \{0,1\}^k$ of bitvectors, determine where there exists a non-overlapping pair $s \in S, t \in T$.

The basic technique to solve this is divide-and-conquer. Here is a $O(n^{1.6} k)$ time algorithm using divide-and-conquer:

1. Split $S$ and $T$ based upon the first bit position. In other words, form $S_0 = \{s \in S : s_0=0\}$, $S_1 = \{s \in S : s_0 = 1\}$, $T_0 = \{t \in T : t_0 = 0\}$, $T_1 = \{t \in T : t_0 = 1\}$.

2. Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$. If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

Since all bitvectors are chosen at random, we can expect $|S_b| \approx |S|/2$ and $|T_b| \approx |T|/2$. Thus, we have three recursive calls, and we've reduced the size of the problem by a factor of two (both sets are reduced in size by a factor of two). After $\lg \min(|S|,|T|)$ splits, one of the two sets is down to size 1, and the problem can be solved in linear time. We get a recurrence relation along the lines of $T(n) = 3T(n/2) + O(nk)$, whose solution is $T(n) = O(n^{1.6} k)$. Accounting for running time more precisely in the two-set case, we see the running time is $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$.

This can be further improved, by noting that if $k \ge 2.5\lg n+100$, then the probability that a non-overlapping pair exists is exponentially small. In particular, if $x,y$ are two random vectors, the probability that they're non-overlapping is $(3/4)^k$. If $|S|=|T|=n$, there are $n^2$ such pairs, so by a union bound, the probability a non-overlapping pair exists is at most $n^2 (3/4)^k$. When $k \ge 2.5 \lg n+100$, this is $\le 1/2^{100}$. So, as a pre-processing step, if $k \ge 2.5 \lg n + 100$, then we can immediately return "No non-overlapping pair exists" (the probability this is incorrect is negligibly small), otherwise we run the above algorithm.

Thus we achieve a running time of $O(n^{1.6} \min(k, \lg n))$ (or $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$ for the two-set variant proposed above), for the special case where the bitvectors are chosen uniformly at random.

Of course, this is not a worst-case analysis. Random bitvectors are considerably easier than the worst case -- but let's treat it as a warmup, to get some ideas that perhaps we can apply to the general case.

Lessons from the warmup

We can learn a few lessons from the warmup above. First, divide-and-conquer (splitting on a bit position) seems helpful. Second, you want to split on a bit position with as many $1$'s in that position as possible; the more $0$'s there are, the less reduction in subproblem size you get.

Third, this suggests that the problem gets harder as the density of $1$'s gets smaller -- if there are very few $1$'s among the bitvectors (they are mostly $0$'s), the problem looks quite hard, as each split reduces the size of the subproblems a little bit. So, define the density $\Delta$ to be the fraction of bits that are $1$ (i.e., out of all $nk$ bits), and the density of bit position $i$ to be the fraction of bitvectors that are $1$ at position $i$.

Handling very low density

As a next step, we might wonder what happens if the density is extremely small. It turns out that if the density in every bit position is smaller than $1/\sqrt{k}$, we're guaranteed that a non-overlapping pair exists: there is a (non-constructive) existence argument showing that some non-overlapping pair must exist. This doesn't help us find it, but at least we know it exists.

Why is this the case? Let's say that a pair of bitvectors $x,y$ is covered by bit position $i$ if $x_i=y_i=1$. Note that every pair of overlapping bitvectors must be covered by some bit position. Now, if we fix a particular bit position $i$, the number of pairs that can be covered by that bit position is at most $(n \Delta(i))^2 < n^2/k$. Summing across all $k$ of the bit positions, we find that the total number of pairs that are covered by some bit position is $< n^2$. This means there must exist some pair that's not covered by any bit position, which implies that this pair is non-overlapping. So if the density is sufficiently low in every bit position, then a non-overlapping pair surely exists.

However, I'm at a loss to identify a fast algorithm to find such a non-overlapping pair, in these regime, even though one is guaranteed to exist. I don't immediately see any techniques that would yield a running time that has a sub-quadratic dependence on $n$. So, this is a nice special case to focus on, if you want to spend some time thinking about this problem.

Towards a general-case algorithm

In the general case, a natural heuristic seems to be: pick the bit position $i$ with the most number of $1$'s (i.e., with the highest density), and split on it. In other words:

1. Find a bit position $i$ that maximizes $\Delta(i)$.

2. Split $S$ and $T$ based upon bit position $i$. In other words, form $S_0 = \{s \in S : s_i=0\}$, $S_1 = \{s \in S : s_i = 1\}$, $T_0 = \{t \in T : t_i = 0\}$, $T_1 = \{t \in T : t_i = 1\}$.

3. Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$. If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

The challenge is to analyze its performance in the worst case.

Let's assume that as a pre-processing step we first compute the density of every bit position. Also, if $\Delta(i) < 1/\sqrt{k}$ for every $i$, assume that the pre-processing step outputs "An overlapping pair exists" (I realize that this doesn't exhibit an example of an overlapping pair, but let's set that aside as a separate challenge). All this can be done in $O(nk)$ time. The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be? I'm not sure, but here are a few observations that might help. Each level of recursion reduces the problem size by about $n/\sqrt{k}$ bitvectors (e.g., from $n$ bitvectors to $n-n/\sqrt{k}$ bitvectors). Therefore, the recursion can only go about $\sqrt{k}$ levels deep. However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than $3^{\sqrt{k}}$ leaves), so I'm not sure what running time this should lead to.

Answer 2

Faster solution when $n \approx k$, using matrix multiplication

Suppose that $n = k$. Our goal is to do better than an $O(n^2k) = O(n^3)$ running time.

We can think of the bitvectors and bit positions as nodes in a graph. There is an edge between a bitvector node and a bit position node when the bitvector has a 1 in that position. The resulting graph is bipartite (with the bitvector-representing nodes on one side and the bitposition-representing nodes on the other), and has $n + k = 2n$ nodes.

Given the adjacency matrix $M$ of a graph, we can tell if there is a two-hop path between two vertices by squaring $M$ and checking if the resulting matrix has an "edge" between those two vertices (i.e. the edge's entry in the squared matrix is non-zero). For our purposes, a zero entry in the squared adjacency matrix corresponds to a non-overlapping pair of bitvectors (i.e. a solution). A lack of any zeroes means there's no solution.

Squaring an n x n matrix can be done in $O(n^\omega)$ time, where $\omega$ is known to be under $2.373$ and conjectured to be $2$.

So the algorithm is:

• Convert the bitvectors and bit positions into a bipartite graph with $n+k$ nodes and at most $nk$ edges. This takes $O(nk)$ time.
• Compute the adjacency matrix of the graph. This takes $O((n+k)^2)$ time and space.
• Square the adjacency matrix. This takes $O((n+k)^\omega)$ time.
• Search the bitvector section of the adjacency matrix for zero entries. This takes $O(n^2)$ time.

The most expensive step is squaring the adjacency matrix. If $n=k$ then the overall algorithm takes $O((n+k)^\omega) = O(n^\omega)$ time, which is better than the naive $O(n^3)$ time.

This solution is also faster when $k$ grows not-too-much-slower and not-too-much-faster than $n$. As long as $k \in \Omega(n^{\omega-2})$ and $k \in O(n^\frac{2}{\omega-1})$, then $(n+k)^\omega$ is better than $n^2 k$. For $w \approx 2.373$ that translates to $n^{0.731} \leq k \leq n^{1.373}$ (asymptotically). If $w$ limits to 2, then the bounds widen towards $n^\epsilon \leq k \leq n^{2-\epsilon}$.

Answer 3

This is equivalent to finding a bit vector which is a subset of the complement of another vector; ie its 1's occur only where 0's occur in the other.

If k (or the number of 1's) is small, you can get $O(n2^k)$ time by simply generating all the subsets of the complement of each bitvector and putting them in a trie (using backtracking). If a bitvector is found in the trie (we can check each before complement-subset insertion) then we have a non-overlapping pair.

If the number of 1's or 0's is bounded to an even lower number than k, then the exponent can be replaced by that. The subset-indexing can be on either each vector or its complement, so long as probing uses the opposite.

There's also a scheme for superset-finding in a trie that only stores each vector only once, but does bit-skipping during probes for what I believe is similar aggregate complexity; ie it has $o(k)$ insertion but $o(2^k)$ searches.

Answer 4

Represent the bit vectors as an $n\times k$ matrix $M$. Take $i$ and $j$ between 1 and $n$.

$$\begin{align} (MM^T)_{ij} = \sum_l M_{il}M_{jl} \end{align}.$$

$(MM^T)_{ij}$, the dot product of the $i$th and $j$th vector, is non-zero if, and only if, vectors $i$ and $j$ share a common 1. So, to find a solution, compute $MM^T$ and return the position of a zero entry, if such an entry exists.

Complexity

Using naive multiplication, this requires $O(n^2k)$ arithmetic operations. If $n=k$, it takes $O(n^{2.37})$ operations using the utterly impractical Coppersmith-Winograd algorithm, or $O(n^{2.8})$ using the Strassen algorithm. If $k=O(n^{0.302})$, then the problem may be solved using $n^{2 + o(1)}$ operations.