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!