3
$\begingroup$

Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.

I am interested in the following problem:

Given $x_1,\dots,x_n \in \{0,1\}^d$ and $y_1,\dots,y_n \in \{0,1\}^d$, I want to determine whether there exists $i,j$ such that $x_i \le y_j$.

How efficiently can this be solved? Pairwise comparison requires $\Theta(n^2)$ comparisons. Can we find a more efficient algorithm?


I would be fine with assuming that the $x$'s and $y$'s come from some reasonable distribution and evaluating using the expected running time, if that helps. We can assume $d$ is small compared to $n$.

Equivalent statement of the problem: Given sets $S_1,\dots,S_n$ and $T_1,\dots,T_n$, determine whether there exists $i,j$ such that $S_i \subseteq T_j$, where all sets are over the universe $\{1,2,\dots,d\}$.

$\endgroup$
  • $\begingroup$ Can we assume that $d = O(\log n)$ ? $\endgroup$ – Marin Shalamanov Jan 20 '17 at 23:45
  • $\begingroup$ @MarinShalamanov, I would prefer an answer that doesn't restrict $d$ to be that small, if possible. $\endgroup$ – D.W. Jan 21 '17 at 1:26
  • $\begingroup$ @D.W. It is a bit late to see your comment, I had another algorithm in mind but it was a bit complicated and I wasn't quite sure if it is correct, but I simplified it and provide something which works for small $d$. In fact vertices of the graph that I defined are some sort of representative for some sort of clusters (we can define artificial partial order on elements). We can make it a bit more clever to rely on $n$ not $d$ but needs some works and preciseness. $\endgroup$ – Saeed Jan 21 '17 at 1:30
  • 2
    $\begingroup$ @Saeed, indeed -- I apologize! Your algorithm is very clever and quite nice, and might be a good building block for handling larger $d$ as well. $\endgroup$ – D.W. Jan 21 '17 at 1:32
7
$\begingroup$

This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? (I believe the reduction is folklore and appears in several places, but one concrete reference is the arxiv paper "Into the Square".) In turn, this disjointness problem is identical to the (gradually becoming infamous) Orthogonal Vectors (OV) problem.

Therefore, algorithms for OV apply directly to this problem. Hence the problem can be solved in $O(2^d \cdot n)$ time, $O(n^{2-1/O(\log(d/\log n))})$ time, and so on (see for example, this SODA'15 paper). Also, there is an $\tilde{O}(n + 2^d)$ time algorithm (I can give it, if you're interested). Furthermore, fine-grained hardness results for OV apply to the problem as well. For example, if it could be solved in $n^{1.999} 2^{o(d)}$ time in the worst case, then the Strong Exponential Time Hypothesis is false -- but don't let that stop you ;)

The "average case" (depending on how you define it) is generally easier and is (as far as we know) unrelated to Strong ETH; partial search data structures (such as Rivest's work on partial search from the 1970s) can be used to solve the average case in subquadratic time.

$\endgroup$
  • 1
    $\begingroup$ I am not the OP, but I am interested in your $\tilde{O}(n + 2^d)$ time algorithm. $\endgroup$ – jbapple Jan 21 '17 at 23:05
  • $\begingroup$ It looks to me that Saeed's answer already suggests such an algorithm: build the "directed hypercube" DAG of $d2^d $ edges, mark the $n$ nodes which are in your input, and check if there's a path between two marked nodes. By dynamic programming ("propagating" the marks) this can be checked in one pass over the DAG by visiting nodes in increasing order of Hamming weight, spending $O(d) $ time at each node to check if a predecessor was marked. $\endgroup$ – Ryan Williams Jan 21 '17 at 23:47
  • $\begingroup$ Maybe it is better to refer to my answer instead of writing "I can give it, if you're interested". $\endgroup$ – Saeed Jan 22 '17 at 12:40
  • $\begingroup$ I had a different algorithm in mind, based on FFT. I admit I didn't look too closely at your original answer. $\endgroup$ – Ryan Williams Jan 22 '17 at 14:48
  • 2
    $\begingroup$ Think of the input as a mulitilinear polynomial in d variables (one variable in each dimension) and n monomials. To check for an orthogonal pair (equivalent to subset containment) you want to check if this polynomial squared has a monomial with no squares (multilinear monomial). You can do that in Otilde (2^d) time using a divide and conquer FFT like algorithm. $\endgroup$ – Ryan Williams Jan 22 '17 at 16:45
3
$\begingroup$

Let suppose $d\le \log n$. We can define a DAG $D$ on $2^d$ vertices $v_1,\ldots,v_{2^d}$, we add edge from $v_i$ to $v_j$ in $D$ if the following conditions hold:

  1. bit representation of $i$ is smaller than bit representation of $j$ (w.r.t. the definition of $\le$ in the question), and
  2. bit representation of $j$ has exactly one additional $1$ compare to $i$.

For example we have an edge $1100\rightarrow 1101$ and an edge $1100\rightarrow 1110$ but there is no edge between $1100$ and $1111$ or there is no edge between $1101$ and $1110$.

Find corresponding vertices of $x_i$'s in this DAG ($x_i$ represents an integer $\ell$ and it corresponds to $v_\ell$) and colour those vertices. Call a coloured vertex $v$ a coloured source (or source), if there is no other coloured vertex which reaches $v$. With one BFS (from node 0), we can find all source vertices. Erase all colours (just a colour not vertices) except source colours. Find corresponding vertices of $y_i$'s and colour them with another colour. Start from one of the source vertices and run a BFS, once we find another coloured vertex we output that vertex together with the source, otherwise we mark the visited vertices of the graph and we continue BFS for other sources and over unvisited vertices. It is not hard to show that this algorithm finds a pair if it exists.

Time complexity: There are $2^d$ vertices in the graph, every node has at most $d$ outgoing edges so total number of edges in the graph is at most $2^d d$. So the algorithm is $O(n\log n)$.

If $d$ is arbitrary, the above algorithm is $O (n+d 2^d)$, and per lowerbound in Ryan Williams answer, it is essentially tight.

$\endgroup$
  • $\begingroup$ Nice! Can we use your algorithm as a building block to handle the case $d \gg \log n$, by restricting to a random subset of coordinates? Suppose we define $d^* = (2/\lg(8/3)) \lg n \approx 1.4134 \lg n$, and assume $d^* < d$. Randomly pick a subset of $d^*$ coordinates and restrict the $x_i$'s and $y_i'$ to those $d^*$ positions, obtaining $x_i^*,y_i^*$. Now apply your algorithm to the $x_i^*,y_i^*$'s to find all pairs $i,j$ such that $x_i^* \le y_j^*$. This takes $O(n^{1.4134} \log n)$ time. (continued) $\endgroup$ – D.W. Jan 21 '17 at 1:51
  • $\begingroup$ We expect to find $O(n^2 (3/4)^{d^*}) = O(n^2 \cdot n^{-0.5866}) = O(n^{1.41334})$ such pairs $i,j$ (since a fixed pair $x_i,y_j$ has a probability $3/4$ of meeting the condition in each selected coordinate), and for each such pair $i,j$ we can test whether $x_i \le y_j$. It looks like the total running time is $O(n^{1.4134} \log n)$. Does this sound right? $\endgroup$ – D.W. Jan 21 '17 at 1:53
  • $\begingroup$ @D.W. It seems this is a precise randomised algorithm, and as you explained sounds the best possible when we want to find all pairs. $\endgroup$ – Saeed Jan 21 '17 at 2:00
  • $\begingroup$ BTW I had something else in mind, I didn't think about randomised algorithm at all. It is very cool and nit though. I'm very sleepy right now, I'll be back tomorrow and will think once more about it and if I get something reasonable will update the answer and inform you. $\endgroup$ – Saeed Jan 21 '17 at 2:02
  • $\begingroup$ I'll put here my ideas for $O(n d + d 2^d)$ solution. Maintain a hash set $M$. 1. Iterate all sets $T_i$ (all the y's). For $T_i$ generate all of it's subsets and put each of them in $M$. This shall be done is top-down manner, i.e. generate the bigger subsets first. If we reach a subset $X$ that is already in $M$, we don't consider the subset of $X$ later. Thus for all iterations there'll be at most $2^d$ insertions in $M$, and exactly that much subsets will be generated. 2. Iterate all sets $S_i$ (all the x's). For each $i$, check if $M$ contains $hash(S_i)$. If so we found a pair. $\endgroup$ – Marin Shalamanov Jan 21 '17 at 5:47
2
$\begingroup$

Here is a divide-and-conquer algorithm with running time $O(n^{1.585})$, for arbitrary $d$, assuming the values are "random" and uniformly distributed.

Let $X^0$ denote the set of $x_i$'s that start with a 0 bit, and $X^1$ the set of $x_i$'s that start with a 1 bit. Similarly define $Y^0$ and $Y^1$ to be the set of $y_i$'s that start with a 0 or 1 bit, respectively. We expect that there will be about $n/2$ elements in each of these sets.

Now we'll recursively check whether there is an element of $X^0$ that is $\le$ an element of $Y^0$; an element of $X^0$ that is $\le$ an element of $Y^1$; or an element of $X^1$ that is $\le$ an element of $Y^1$. The recursion bottom out when the set is of constant size. The running time of this algorithm satisfies the recurrence

$$T(n) = 3 T(n/2) + O(1),$$

which has the solution $T(n) = O(n^{\lg 3}) = O(n^{1.585})$.

$\endgroup$
  • 1
    $\begingroup$ You may add your comments on my answer here. That looks actually promising. $\endgroup$ – Saeed Jan 21 '17 at 2:04

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.