# Test if there are two subsets which cover a set

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?

• This sounds somewhat similar to the 3SUM problem. – Yuval Filmus Mar 4 '13 at 20:05
• @Yuval Filmus I also thought so, but so far I did not find a simple reduction – user695652 Mar 4 '13 at 21:01
• 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? – frafl Mar 6 '13 at 14:28

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