title: Reducing 3-SAT to Vertex Cover?
body: <p>Can someone explain to me in the most simplest possible way, how to reduce <code>3-SAT</code> to <code>Vertex Cover</code> ? I am following the explanation <a href="http://web.mit.edu/~neboat/www/6.046-fa09/rec8.pdf" rel="nofollow">here</a>(scroll to page 4 bottom). I understand the basic setup of having two "gadgets": the 2-node variable gadgets and 3-node clause gadgets. I also understand the formula <code>k = variables + 2 clauses</code> as the minimum number of nodes required to cover all the edges. What I don't understand is how this set up proves that if there exist a <code>k-covering</code>, then the boolean expression in CNF is satisfiable. Examples with expressions that are satisfiable and not satisfiable would be helpful. Also, once the <code>3-SAT</code> problem is converted to a <code>k-covering</code>, does it provide a means to identify which value( <code>true</code> or <code>false</code>) should be assigned to each variable so as to satisfy the boolean expression ? Thanks for any help.</p>