# What is the LP gap of vertex cover in planar graphs?

What is the LP gap of vertex cover in planar graphs?

The LP I refer to is min $\sum_{e \in E } c_e x_e \ \$ subject to $\ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E$
$c_e \geq 0$ are costs of the vertices

Also is there an LP with a smaller gap?

(I posted this in mathstackexchange where it was labelled offtopic if it is offtopic here please tell me where I should post this.)

The vertex cover LP gap is $$\frac32$$ for planar graphs. The $$\frac32$$ follows by looking at an extreme point optimal LP solution with values in $$\{0, \frac12, 1\}$$. Let $$V_{i}$$ be the set of vertices with LP value $$i$$ for all $$i \in \{0, \frac12, 1\}$$. Now we create an integral vertex cover. In this vertex cover take all the $$V_1$$vertices. Now, look at any $$4$$ coloring of the graph. This coloring will partition $$V_{\frac12}$$ into 4 part. Now to our vertex cover, we add all the vertices in $$V_{\frac12}$$ except the part with a maximum cost. It is easy to see that what we get is a vertex cover of cost at most $$\frac32$$ times the LP value.
$$K_4$$ gives a tight lower bound of $$\frac32$$.