Question

Let $\mathbf{SET}\mathbf{-}\mathbf{SPLITTING}\mathbf{}$collection of subsets of S, for some $\mathbf{k}>\mathbf{0}$, such that elements of S can be colored red or blue so that no Ci has all its elements colored with the same color}. Show that $\mathbf{SET}-\mathbf{SPLITTING}$is NP-complete.

Short answer

This concludes that satisfying assignment for$\varphi$.

Step-by-step solution

Step 1:prove that Set-splitting value

1.SET – SPLITING is in NP :

SET – SPLITING is in NP because we can verify in polynomial time that no subsetis monochromatic.

3 SAT ${⩽}_{\text{p}}$SET - SPLITING :

To prove that the problem is NP complete, we give a polynomial time reduction from S A T to SETSPLITING$\varphi$.

Assignment of the Set

The splitting is done as follows:

If is satisfiable, consider a satisfying assignment.

If we color all the true literals red, all the false ones are blue, and y blue, then every subset$C_i$ of$S$ has at least one red element (because it is satisfiable and it also contain one blue element y.

In addition, for a given splitting $⟨S,C⟩$, we can able to set the literals that are colored differently from y to true.

In the same way, we can able to set the literals that have the same color as y to false.

This concludes that satisfying assignment for $\varphi$.

Thus, SET - SPLITTING is NP-Complete.