1
$\begingroup$

There are plenty of resources online discussing 3-SAT reductions to Independent Set or Vertex Cover problem. I am unable to find a resource which states that a satisfiable assignment to 3-SAT results in a vertex cover or an independent set which is optimum for the graph induced by 3-SAT in its reduction.

Say, I have a 3-SAT formula with n boolean variables and c clauses, which is reduced to an Independent Set problem on a graph. Its known that if the 3-SAT is satisfiable, then there exists an independent set of size c in the reduced graph. Is this the maximum independent set? Logically, adding one more vertex to the set will violate the property of the independent set, so it should be the maximum independent set. Can someone confirm this?

Now, if I do a reduction to vertex cover graph, a satisfiable assignment should correspond to a vertex cover of size n + 2c. Is this the minimum vertex cover achievable?

Any suggestions will be highly appreciated. Thanks!

$\endgroup$
  • 1
    $\begingroup$ "Is this the maximum independent set?" Yes, since an independent set can have at most one node taken from the triangle that corresponds to a clause and there are $c$ triangles. Does that answer your first question? $\endgroup$ – Apass.Jack Dec 7 '18 at 17:52
  • $\begingroup$ Yes. Will the vertex cover be the minimum? Thanks! $\endgroup$ – pg2455 Dec 7 '18 at 18:05

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.