Question

vertex_cover
extream_point

Consider the vertex cover problem.

1. Prove that any extreme point of the linear program

$\begin{array}{ll} \min & \sum_{i \in V}w_ix_i \\ \text{s.t} \\ \forall (i, j) \in E & x_i + x_j \geq 1 \\ \forall i \in V & x_i \geq 0 \end{array}$

has the property that $x_i \in \{0, \frac{1}{2}, 1\}$ for all $i \in V$. (Recall that an extreme point $x$ is a feasible solution that cannot be expressed as $\lambda x^1 + (1 - \lambda)x^2$ for $0 < \lambda < 1$ and feasible solutions $x^1$ and $x^2$ distinct from $x$.)

2. Give a $\frac{3}{2}$-approximation algorithm for the vertex cover problem when the input graph is planar. You may use the facts that polynomial-time LP solvers return extreme points, and that there is a polynomial-time algorithm to 4-color any planar graph (i.e. the algorithm assigns each vertex one of four colors such that for any edge $(i, j) \in E$, vertices $i$ and $j$ have been assigned different colors).

1

1. Assume for contradiction that $x^*$ is an extreme point that does not have this property, and define $x^- = \{x_i : 0 < x_i < \frac{1}{2}\}$ and $x^+ = \{x_i : \frac{1}{2} < x_i < 1\}$ and define two points:
$\begin{array}{ll} y_i = \begin{cases} x_i + \epsilon & x_i \in x^+ \\ x_i - \epsilon & x_i \in x^- \\ x_i & \text{otherwise} \end{cases} & z_i = \begin{cases} x_i - \epsilon & x_i \in x^+ \\ x_i + \epsilon & x_i \in x^- \\ x_i & \text{otherwise} \end{cases} \end{array}$
Clearly $x^* = \frac{1}{2}(y + z)$ and $y \neq z \neq x$. We now show that for a small enough $\epsilon$, $y$ and $z$ are feasible:
Consider a constraint $x_i \geq 0$ then for small enough epsilon this constraint is still feasible. Now consider a constraint $x_i + x_j \geq 1$ if the constraint is not tight then for small enough $\epsilon$ the constraint is still feasible, if the constraint is tight then either (w.l.o.g) $x_i \in x^+, x_j \in x_j^-$ and the constraint is still feasible or $x_i = x_j = \frac{1}{2}$ and the constraint is still feasible.
2. Consider an extreme solution, $x^*$, to the LP and a 4-coloring of the vertices. Define $V_1 = \{i : x_i = 1\}$ and $V_{\frac{1}{2}} = \{i : x_i = \frac{1}{2}\}$ and let $V^1, \dots, V^4$ the partition of $V_{\frac{1}{2}}$ according to the 4-coloring. It is easy to see that $V_1$ plus any 3 sets out of $V^1, \dots, V^4$ form a feasible vertex cover. If we take the three sets out of $V^1, \dots, V^4$ with the minimum cost then the total cost of our solution is at most $2 \frac{3}{4}$ the value of the LP and thus a $\frac{3}{2}$-approximation algorithm.