Reduction of 3-SAT to Vertex Cover?

Question

Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$?

I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of having two "gadgets": the 2-node variable gadgets and 3-node clause gadgets.

I also understand the formula $k = variables + 2\:clauses$ as the minimum number of nodes required to cover all the edges. What I don't understand is how this setup proves that if there exists a $k\text-covering$, then the boolean expression in CNF is satisfiable.

Examples with expressions that are satisfiable and not satisfiable would be helpful. Also, once the $3SAT$ problem is converted to a $k\text-covering$, does it provide a means to identify which value (true or false) should be assigned to each variable so as to satisfy the boolean expression?

Answer 1

To show that Vertex Cover and 3SAT is "equivalent", you have to show that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step.

Assuming you are familiar with how the reduction is done, (if not ,refer to the document).

Since you only asked about how this setup proves that if there exists a k-covering, then the boolean expression in CNF is satisfiable.

This is effectively the "only if" part to the proof that the two are "equivalent". So all you need to do is to show that as long as there is a k Vertex Cover for the graph constructed in the reduction, you have a satisfying solution to 3SAT.

The proof:

Since there is a k Vertex Cover, then one and only one node of each of the variable gadgets must be in the Vertex Cover. (This is because k = variables+2clauses,if you don't choose one of the variable in the variable gadget then the middle connection in the gadget is not incident, and if you choose in one gadget, you will end up with variables + 1 + 2 clauses, we'll show that you must choose 2 nodes in each clause gadget in the next sentence.)

We must have 2 nodes in each clause gadget because if we don't, then one of the connection in the clause gadget is not incident.

So set the variable corresponding to the one node that is selected in each of the variable gadgets to TRUE.

Now we have two scenarios for each of the clause gadgets:

One: A gadget can have a connection with a variable Node that is set to TRUE. In this case the gadget has a variable which is TRUE, the gadget is therefore satisfied.

Two: A gadget does not have a connection with a variable Node set to True. Then it must select all 3 of its Nodes to make the edges all incident. And that is not possible when we have a k Vertex Cover.

Hope this answers your question :))