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?

  • 1
    $\begingroup$ I suggest you keep reading the document. The correctness proof is on page 5. $\endgroup$ – Yuval Filmus Sep 3 '17 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.