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