Rounding for Vertex Cover
Recall the LP-rounding algorithm for weighted Vertex Cover:
Then return $C = \{v_i \in V : x_i \ge 1/2\}$.
Part A
Suppose we instead include $v_i$ when $x_i \ge 1/3$. What happens?
Part B
Suppose we instead include $v_i$ when $x_i \ge 2/3$. What happens?
Part C
Consider this alternative rounding rule: for each edge $(v_i,v_j)$, include the endpoint with larger LP value (break ties toward larger index). Equivalently,
$C := \{ v_i : \exists (v_i,v_j)\in E \text{ with } (x_i > x_j) \text{ or } (x_i = x_j \text{ and } i > j)\}$.
Which statement is true?
Part A: Validity is preserved since every edge has $x_i+x_j\ge 1$, so at least one endpoint is at least $1/2$, and therefore at least $1/3$.
The cost bound becomes $w(C)\le 3\sum_i w(v_i)x_i$, giving a 3-approximation.
Part B: Validity can fail: if an edge has LP values $(1/2,1/2)$, neither endpoint is selected by a $2/3$ threshold.
Part C: This rule always covers each edge (one endpoint is chosen per edge), and selected vertices always satisfy $x_i\ge 1/2$, so it can improve over standard threshold rounding on some instances.
However, the worst-case approximation guarantee remains essentially 2 (it can still be above 1.999).