Skip to main content
2 of 2
tight lower bound

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