Efficient way to choose set from including conditions on sets - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:03:49Z https://cs.stackexchange.com/feeds/question/80338 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/80338 1 Efficient way to choose set from including conditions on sets neutron-byte https://cs.stackexchange.com/users/68776 2017-08-22T16:53:41Z 2018-07-25T06:00:34Z <p>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:</p> <ul> <li>The set $Y$ contains exactly $n$ elements: $|Y| = n$</li> <li>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$</li> </ul> <p><strong>EXAMPLE.</strong> Let $m = 5$, $n = 2$. We are given the following conditions. Set $Y$ contains...</p> <ul> <li>1 element out of $\{ 2, 3, 4, 5 \}$, $\quad$ ($a_1 = 1$)</li> <li>2 elements out of $\{ 1, 2, 3, 4 \}$, $\quad$ ($a_2 = 2$)</li> <li>1 element out of $\{ 1, 3, 4, 5 \}$. $\quad$ ($a_3 = 1$)</li> </ul> <p>$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.</p> <p>Of course, there may be many solutions, up to $\binom{m}{n}$ to be specific. </p> <p><strong>QUESTIONS.</strong> I have the following two questions:</p> <ul> <li>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?</li> <li>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?</li> </ul> <p><strong>MY APPROACHES.</strong> 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.</p> <p>I would appreciate any kind of help and material.</p> https://cs.stackexchange.com/questions/80338/-/80560#80560 1 Answer by j_random_hacker for Efficient way to choose set from including conditions on sets j_random_hacker https://cs.stackexchange.com/users/1984 2017-08-28T21:01:57Z 2017-08-28T21:01:57Z <p>I think it should be straightforward to reduce <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability" rel="nofollow noreferrer">One-in-3SAT</a> 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).</p> <p>Showing this reduction would show that the problem is NP-hard, indicating that a polynomial-time solution is very unlikely.</p>