Problem 2. Consider the CNF x1bar means complement of x1 etc. (x1 or x2bar or x3

Question

Problem 2. 
Consider the CNF x1bar means complement of x1 etc.
(x1 or x2bar or x3) and (x1bar or x2 or x3) and (x1 or x3bar)  and (x2 and x3bar or x4)

Convert this to the graph G=(V,E) so that this G will have a clique of size 4 if and only if CNF is satisfiable.  Will G  have a clique of size 4?

Change largest vertex cover to smallest vertex cover. - largest is easy!

Problem 3. 
For the graph G=(V,E) above, construct Gbar., the complement graph.   What is the largest clique in G? what is the largest vertex cover in Gbar?

Explanation / Answer

(Detailed proof can be found on page 947 – 949 in the textbook)

Note: The key to the above proof is an appropriate reduction. The reduction needs to ensure the "if and only if" relationship.

Vertex Cover (VC)

Definition: Given a graph G(V, E), a vertex cover S is a subset of V, that covers all the edges in E. The size of a vertex cover is the number of vertices in it.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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