9
$\begingroup$

Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary. After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. I want to identify any sets $B \in \mathcal X$ with $B \subseteq A$.

The obvious algorithm (without any preprocessing) takes time $O(n |\cal X|)$ -- you simply test $A$ against each $B \in \mathcal X$ separately. Is there anything better than this?

If it helps, you can assume that, for any $A$, the total number of matches $B \in \mathcal X$ is bounded by something like $O(1)$.

$\endgroup$
3
$\begingroup$

This is not an answer. It is a simple but long observation. I hope it will be useful.

The decision version of your problem is: Does $\cal X$ contain a subset of $A$?

This problem is related to the problem of evaluating monotone boolean functions of $n$ variables. A subset of $\{1,\ldots,n\}$ is equivalent to an $n$-bitstring, so the family $\cal X$ is equivalent to a boolean function $f$ of $n$ variables. Given a function $f$, one can define the least monotone function that is not bigger than $f$, namely $g(y)=(\exists x\subseteq y,\,f(x))$. The original problem is then reduced to evaluating $g(A)$. Conversely, the problem of evaluating a monotone boolean function can be reduced to the original problem, either naively by taking $f=g$ or by choosing an $f$ that makes $\cal X$ smaller.

In practice BDDs tend to work well. So one possible approach is to build the BDD for $f$, derive from it the BDD for $g$, and then evaluate $g$. The average size of the BDD for $g$ must be $\Omega\left(\binom{n}{n/2}\right)$, because there are many monotone boolean functions. Hence, in theory this is a bad solution.

But (1) a better analysis might be possible and (2) there might be tweaks to this approach that make it better. For example, I didn't use in any way the correlation between the size of $\cal X$ and the size of $g$'s BDD. (There must be a correlation, but I don't know if it is simple or usable here.)

For completeness, a simple algorithm for computing the BDD for $g$ from the BDD for $f$ is the following. $$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$$ Here $\lor$ is the standard or-operation on BDDs.

$\endgroup$
  • 2
    $\begingroup$ Isn't this more or less equivalent to precalculating the answer for each subset of $\{1,2,...,n\}$, caching all the results in a binary tree of size $2^n$, and then looking up the right result (in time $O(n)$) when you're given $A$? $\endgroup$ – mjqxxxx Jan 3 '12 at 20:48
  • $\begingroup$ Using exponential space to store preprocessed data sounds like cheating to me, although it is not prohibited in the question. But I may be biased toward the Church of Worst-Case Complexity. $\endgroup$ – Tsuyoshi Ito Jan 4 '12 at 14:13
  • $\begingroup$ mjqxxxx and Tsuyoshi: I agree with both of you. I rewrote the text so that, I hope, it is more clear that I agree. :) $\endgroup$ – Radu GRIGore Jan 5 '12 at 0:36
3
$\begingroup$

Perhaps you can use an "information retrieval" technique: in the preprocessing phase, build an inverted index (in your case a simple $n \times | {\cal X}|$ bidimensional array is enough) that maps an element $x_i \in \{1,...,n\}$ to the sets in $\cal X$ that contain it: $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \} $.

Set up an integer array $occ$ of length $|\cal X|$.

Then for each $y_i \in A$ retrieve $inv(y_i)$, and for each $X_j \in inv(y_i)$ do $occ[j] = occ[j]+1$

At the end the sets you need are those for which $|X_j|=occ[j]$.

You can arbitrarily speed up the process (at the cost of exponential space) by indexing two or more elements together.

$\endgroup$

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.