- Set splitting
Set splitting is a logical
NP-Complete problem which is defined as follows:::"Instance": A finite set S and a collection C of finite subsets of S ;
::"Query": Can the elements of S be colored with two colors, say red and green, so that no set X ∈ C has all elements colored with the same color?
As an example, suppose that
S = {1, 2, 3, 4, 5, 6}
and
C = 1, 2}, {3, 4, 5}, {2, 3, 6}, {1, 4, 6}, {2, 5
Demonstration that set-splitting is NP-Complete
To prove SET-SPLITTING is NP-Complete, we need to show
*SET-SPLITTING is NP and
*SET-SPLITTING isNP-hard .To show that SET-SPLITTING is NP, given a coloring, it is easy to verify in polynomial time that no set is monochromatic. To prove that SET-SPLITTING is NP-hard, we reduce 3SAT to it.
Let φ be a 3CNF formula with variable set V . Construct the fol lowing instance of SET-SPLITTING. The set of elements S is {F } ∪ V ∪ { ¯ X : X ∈ V }. Here F is a new element not related to any variable. Each other element corresponds to a variable or its negation.
Build the collection of sets C as follows. For each variable X in φ, construct a set SX = {X, ~X}. For each clause c (e.g. X ∨ Y ∨ ~Z ), construct a set Sc = {X, Y , ~Z , F }. Here F is a new element not related to any variable. (There is only one such element F — it is the same across all sets built for clauses.) So, the reduction is f (φ) = (S, C ) where S and C are as described above.
Clearly the reduction is polynomial time.
To finish we prove that φ is satisfiable if and only if (S, C ) can be colored so that no set is monochromatic. ( ⇒) Suppose φ is satisfiable. Fix some satisfying assignment.
Consider the following coloring of the elements in S . Color the element F ’red’. For each variable X that is assigned ’false’, color the elements X and ~X ’red’ and ’green’, respectively. For each variable X that is assigned ’true’, color the elements X and ~X ’green’ and ’red’, respectively. As long as the assignment was satisfying, this coloring makes no set monochromatic. For each variable X , the set SX = {X, ~X } has one red and one green element. For each clause c, the set Sc has at least one red element (F ) and, because some literal in the clause has a value of true, Sc has at least one ’green’ element.
Thus, (S, C ) ∈ SET-SPLITTING.
(⇐) Suppose (S, C ) ∈ SET-SPLITTING. Fix some coloring of S with two colors such that every set has at least one element of both colors. Consider the fol lowing assignment to the variables of φ. For each variable X , assign it ’true’ if its color differs from that of the element F . Assign X ’false’ if its color is the same as that of the element F . Then each clause c in φ is satisfied, because the set Sc has at least one element X or ¯ X that is colored differently than F . Thus, ∈SAT.
Wikimedia Foundation. 2010.
