Efficient way to choose set from including conditions on sets

Question

Let $m, n \in \mathbb{N}$ and $n \le m$. Given $k$ subsets $X_1, X_2, \dots, X_k$ of $\{ 1, 2, \dots, m \}$ and $k$ nonnegative integers $a_1, a_2, \dots, a_k$, find all subsets $Y$ of $\{ 1, 2, \dots, m \}$ satisfying the following conditions:

• The set $Y$ contains exactly $n$ elements: $|Y| = n$
• The set $X_i$ has exactly $a_i$ elements with $Y$ in common: $\forall 1 \le i \le k: |X_i \cap Y| = a_i$

EXAMPLE. Let $m = 5$, $n = 2$. We are given the following conditions. Set $Y$ contains...

• 1 element out of $\{ 2, 3, 4, 5 \}$, $\quad$ ($a_1 = 1$)
• 2 elements out of $\{ 1, 2, 3, 4 \}$, $\quad$ ($a_2 = 2$)
• 1 element out of $\{ 1, 3, 4, 5 \}$. $\quad$ ($a_3 = 1$)

$Y = \{ 1, 2 \}$ is a unique solution. It is necessary to have $1 \in Y$, else we must select two elements of $\{ 2, 3, 4 \}$ (2nd set without $1$), which is a subset of the 1st set. Now consider the 3rd set. If we select $3, 4$ or $5$ instead of $2$, $Y$ would contain two elements from 3rd set.

Of course, there may be many solutions, up to $\binom{m}{n}$ to be specific.

QUESTIONS. I have the following two questions:

• Are there any algorithms better than trivial brute-force to find all solutions to an instance of this problem? Do these algorithms fulfill known lower bounds?
• Given that there exists a unique solution, can we use this extra knowledge to do better than in the general case in terms of time complexity?

MY APPROACHES. Obviously, it is possible to enumerate all $\binom{m}{n}$ subsets and check the conditions. At least for the last step (I know, the first step causes the lack of efficiency) I can think of some improvements. First, we may represent the sets as boolean arrays of size $m$. When iterating over the possible solutions, we may compute $X_i \cap Y$ in time $\mathcal{O}(m)$ resulting in an $\mathcal{O}\left(m\binom{m}{n}\right)$ solution. Additionally, if there is a set $X_i$ with $|X_i| = a_i$ we are lucky. In this case, we know $X_i \subseteq Y$ and may erase all elements of $X_i$ in the other subsets $X_j$ replacing $a_j$ by $a_j - |X_i \cap X_j|$. But in general, this special case does not occur with certainty.

I would appreciate any kind of help and material.

Answer 1

I think it should be straightforward to reduce One-in-3SAT to this problem: For example, you can create a size-2 set $X_i$ for each variable $x_i$ from the One-in-3SAT instance, and set $a_i=1$ to force that either the variable or its negation is chosen. $n$ will be the number of variables, and you will need additional sets $X_j$ for each clause, with $a_j=1$ (reflecting the constraint that exactly 1 literal in each clause be positive).

Showing this reduction would show that the problem is NP-hard, indicating that a polynomial-time solution is very unlikely.