# Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S

Given a universal set of elements $\mathbf{U} = \{a_1, a_2, .., a_n\}$, a set $\mathbf{R} = \{a_i\} \subset \mathbf{U}$ where $i ϵ \{1, .., n\}$, a set $\mathbf{P} = \{R_1, .., R_m\}$ and a set $\mathbf{C} = \{P_1, P_2, .., P_l\}$, how do I go about finding a set $\mathbf{S} = \{a_1, .., a_n\} \subset \mathbf{U}$ such that at least one set $\mathbf{R}$ from each $\mathbf{P}$ is satisfied and such that the size of $\mathbf{S}$ minimal? I consider the set $\mathbf{R}$ to be satisfied by $\mathbf{S}$ if $\mathbf{R} \subseteq \mathbf{S}$.

This seems similar to set cover problem, but I am not sure how I can approach this.

• I edited to try to spell out the problem a little more explicitly; please check whether my edits are correct. – D.W. Dec 19 '16 at 15:28
• I think there is a typo because you wrote the sets $\mathbf{U}$ and $\mathbf{R}$ as equal and $\mathbf{R}\subset\mathbf{U}$. – drzbir Dec 19 '16 at 15:44
• @Azzo updated the problem statement to clarify that U and R are not necessarily equal – Amit Ambasta Dec 20 '16 at 4:53

## 1 Answer

Your problem is NP-hard, by reduction from Monotone SAT.

Recall that Monotone SAT is (the decision version of) the following problem: given a CNF formula $\varphi$, find a satisfying assignment with the fewest variables set to true.

Now, map each clause, say $x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}$, in $\varphi$ to a set $P=\{R_1,R_2,\dots,R_k\}$ where $R_1=\{x_{i_1}\}$, $R_2=\{x_{i_2}\}$, etc. Finally, form $C$ to be the set of $P$'s obtained in this way from the clauses of $\varphi$. Then a set $S$ satisfies $C$ iff it corresponds to a satisfying assignment for $\varphi$ (including the element $x_i \in S$ corresponds to setting $x_i$ to true in the assignment), so the minimal-size set $S$ that satisfies C corresponds to the minimal-size satisfying assignment for $\varphi$.

Since Monotone SAT is NP-hard, your problem is NP-hard, too.

If you need to try to find an exact solution in practice, you could try formulating your problem as an instance of SAT and feed it to a SAT solver (using binary search over the size of $S$), or you could formulate it as an instance of integer linear programming and feed it to an ILP solver.

• Right, except SAT is of the form, $(A \lor B) \land (A \lor C)$, while the current problem statement is of the form, $((A \land B) \lor (A \land C)) \land ((A \land F) \lor (C \land Q))$. Expanding this is going to be expense – Amit Ambasta Dec 20 '16 at 10:46
• Edit: nm, realized that the second problem is still a SAT problem – Amit Ambasta Dec 20 '16 at 10:51
• @AmitAmbasta, en.wikipedia.org/wiki/Tseytin_transformation – D.W. Dec 20 '16 at 16:06