6
$\begingroup$

Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?

$\endgroup$
  • $\begingroup$ This sounds somewhat similar to the 3SUM problem. $\endgroup$ – Yuval Filmus Mar 4 '13 at 20:05
  • $\begingroup$ @Yuval Filmus I also thought so, but so far I did not find a simple reduction $\endgroup$ – user695652 Mar 4 '13 at 21:01
  • $\begingroup$ What's even more interesting: If there is an $o(nm^2)$-algorithm for 2 sets, would there be an $o(nm^k)$-algorithm for k sets, too? $\endgroup$ – frafl Mar 6 '13 at 14:28
3
$\begingroup$

There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to $$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$ Indeed, if $\chi_U$ is the indicator vector of $U$ then $$ \chi'_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$ The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\{0,1\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h_U = g_{\overline{U}}$. The FFT algorithm uses the basic operation $h_{U \cup \{i\}} = h_U \lor h_{U \cup \{i\}}$. This makes it clear why $\bigvee_U f_U g_U = \bigvee_U f_U h_{\overline{U}}$ is what we want.

$\endgroup$
-2
$\begingroup$

A solution to this problem is the two subsets $U$ and $V$ from $\mathcal{X}$. If we know $U$ upfront, we can answer this question in $O(n*m)$.

So let us examine the case where we would have a unique $U$, this happens when there is an element $a \in S$ is covered only by $U$. We can check this possibility in $O(n*m)$.

Afterwards, we can find $V$ through brute force in $O(n*m)$. If we don't have this possibility, I am not sure whether we can solve it more efficiently.

$\endgroup$
  • 2
    $\begingroup$ In my opinion, I guess it would be more convenient to have this answer as a "comment" .. answering with no "answers" will let some users avoid even checking the question. -- in any case, welcome to this forum. $\endgroup$ – AJed Mar 4 '13 at 17:25

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.