Set splitting

From Wikipedia, the free encyclopedia

Set splitting is Logical NP-Complete problem which is defined as

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}}


To prove SET-SPLITTING is NP-Complete, we need to show

  • SET-SPLITTING is in NP and
  • SET-SPLITTING is NP-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.

 This article is uncategorized.
Please categorize this article to list it with similar articles. (June 2008)