2
$\begingroup$

Given 2 collections of finite sets $A_1,A_2,\ldots,A_m$ and $B_1,B_2,\ldots,B_n$, is there a set $T$ such that: $\left|T \cap A_j\right|\ge 1$, for $j = 1,2,\ldots,m$ and $\left|T \cap B_i\right|\le 1$, for $i= 1,2,\ldots,n$?

I tried doing this problem by considering it as a decision problem (pi). Please suggest me if you have an approach.

$\endgroup$
2
$\begingroup$

You can reduce 3SAT to this problem by converting each variable $v_i$ to two elements $e_{i1}$ and $e_{i2}$ (one for its positive literal and one for its negative literal) and a set $B_i$ containing $e_{i1}$ and $e_{i2}$, and converting each clause $c_j=l_{j1}\vee l_{j2}\vee l_{j3}$ to a set $A_j$ containing elements representing $l_{j1},l_{j2},l_{j2}$.

Now it's not hard to prove this problem is NP-complete using the reduction above.

$\endgroup$
  • $\begingroup$ Can't we solve this problem by decision technique and prove the np completeness? $\endgroup$ – Wajahat Nazal Apr 9 '18 at 20:27
  • $\begingroup$ @WajahatNazal My answer already shows the NP-completeness. What do you mean by decision technique? $\endgroup$ – xskxzr Apr 10 '18 at 2:32

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.