Consider the vertex cover problem.

1. Prove that any extreme point of the linear program

miniVwixis.t(i,j)Exi+xj1iVxi0 \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 xi{0,12,1}x_i \in \{0, \frac{1}{2}, 1\} for all iVi \in V. (Recall that an extreme point xx is a feasible solution that cannot be expressed as λx1+(1λ)x2\lambda x^1 + (1 - \lambda)x^2 for 0<λ<10 < \lambda < 1 and feasible solutions x1x^1 and x2x^2 distinct from xx.)

2. Give a 32\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)E(i, j) \in E, vertices ii and jj have been assigned different colors).



1. Assume for contradiction that xx^* is an extreme point that does not have this property, and define x={xi:0<xi<12}x^- = \{x_i : 0 < x_i < \frac{1}{2}\} and x+={xi:12<xi<1}x^+ = \{x_i : \frac{1}{2} < x_i < 1\} and define two points:

yi={xi+ϵxix+xiϵxixxiotherwisezi={xiϵxix+xi+ϵxixxiotherwise \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=12(y+z)x^* = \frac{1}{2}(y + z) and y̸=z̸=xy \neq z \neq x. We now show that for a small enough ϵ\epsilon, yy and zz are feasible:

Consider a constraint xi0x_i \geq 0 then for small enough epsilon this constraint is still feasible. Now consider a constraint xi+xj1x_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) xix+,xjxjx_i \in x^+, x_j \in x_j^- and the constraint is still feasible or xi=xj=12x_i = x_j = \frac{1}{2} and the constraint is still feasible.

2. Consider an extreme solution, xx^*, to the LP and a 4-coloring of the vertices. Define V1={i:xi=1}V_1 = \{i : x_i = 1\} and V12={i:xi=12}V_{\frac{1}{2}} = \{i : x_i = \frac{1}{2}\} and let V1,,V4V^1, \dots, V^4 the partition of V12V_{\frac{1}{2}} according to the 4-coloring. It is easy to see that V1V_1 plus any 3 sets out of V1,,V4V^1, \dots, V^4 form a feasible vertex cover. If we take the three sets out of V1,,V4V^1, \dots, V^4 with the minimum cost then the total cost of our solution is at most 2342 \frac{3}{4} the value of the LP and thus a 32\frac{3}{2}-approximation algorithm.