### Question

Consider the vertex cover problem.

**1.** Prove that any extreme point of the linear program

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).

### Answers

**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:

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.