Question

True or False: If we have an integer primal solution with cost C and a fractional dual solution with cost at least C/2, the size of the vertex cover corresponding to the primal solution is at most twice the size of the smallest vertex cover. Briefly justify your answer

Answer 1

Answer:

True

Step-by-step explanation:

The size of the vertex cover is atleast twice the size of the maximum edge. Vertex must contain atleast one vertex from the matched edge. Vertex are never the strong dual solutions of each other.