In Cormen's Introduction to Algorithms, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align*} &\sum\limits_{v \in V}w(v)x(v) \tag{35.15} \\ x(u) + x(v) &\geq 1 \text{ for each } u, v \in E \tag{35.16} \\ x(v) & \leq 1 \text{ for each } v \in V \tag{35.17} \\ x(v) &\geq 0 \text{ for each } v \in V. \tag{35.18} \end{align*}$ However, I am wondering why the constraint $x(v) \leq 1$ is even necessary? If it was greater than one, wouldn't the optimal solution still be most optimal? If this isn't the case, could someone please explain why? If it is the case, would you also explain? Thank you.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You could delete this constraint, but it would still be verified in a solution: if there is a solution satisfying all other contraints and $x(v) > 1$ for a certain $v$, then the same solution with $x(v) = 1$ still satisfy the constraints. Since weights are positive, the sum with $x(v) = 1$ would be lesser than the sum with $x(v) > 1$.
