Rounding for Vertex Cover
Recall the LP-rounding algorithm for weighted Vertex Cover:
$$
\begin{aligned}
\text{Minimize} \quad & \sum_{i=1}^{n} w(v_i)\,x_i \\
\text{subject to} \quad & x_i + x_j \ge 1 \quad \forall (v_i,v_j) \in E \\
& 0 \le x_i \le 1 \quad \forall i
\end{aligned}
$$
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?