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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.