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.

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

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.

  • $\begingroup$ 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 $\endgroup$ – Amit Ambasta Dec 20 '16 at 10:46
  • $\begingroup$ Edit: nm, realized that the second problem is still a SAT problem $\endgroup$ – Amit Ambasta Dec 20 '16 at 10:51
  • $\begingroup$ @AmitAmbasta, en.wikipedia.org/wiki/Tseytin_transformation $\endgroup$ – D.W. Dec 20 '16 at 16:06

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.