2. Now recall each k-CNF formula has at most k literals per clause and that the

Question

2. Now recall each k-CNF formula has at most k literals per clause and that the set k-SAT consists of those k-CNF formula that are satisable by some truth assignment to their variables. Consider the following mapping from 2-Color to 2-SAT. Map every vertex x of a graph G onto a Boolean variable X. For each edge (u; v) in G, add clauses (U + V )(U + V ) to an initially-empty CNF formula F. G is 2-colorable if and only if F is 2-satisable. Prove that this is a correct many-one reduction between the two problems.

Explanation / Answer

We will decrease 2-COLORABLE to 2-SAT. Given a diagram G, our decrease creates the accompanying arrangement of conditions: name the vertices of G with factors X for each edge between vertices marked U and V, deliver the provisos (U V) and (U' V').

Plainly this diminished keeps running in polynomial time. We now contend that "yes maps to yes." If G is 2-colorable, at that point pick one of the two hues in a 2-shading of G and dole out the related factors TRUE. Each one of the statements is fulfilled, on the grounds that the best way to neglect to fulfill a proviso is if the two endpoints of a few edges were similar shading.

We contend that "no maps to no." Suppose we have a fantastic task to the arrangement of statements created by the decrease. At that point the two factors related with a given edge must have distinctive truth assignments. Accordingly, on the off chance that we shading the vertices of G related with TRUE factors red, and alternate vertices of G green, we will have created a legitimate 2-shading of G, and subsequently G is 2-colorable.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.