1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @j_random_hacker, this is both k-in-3SAT and weighted SAT. Don't know where you can put constraint $n$. But AFAIK putting AND between NPC problems always is NP-hard problem. $\endgroup$ – rus9384 Aug 24 '17 at 12:17
  • $\begingroup$ @j_random_hacker Convert you comment to an answer? $\endgroup$ – Yuval Filmus Aug 25 '17 at 15:40
1
$\begingroup$

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.

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