5
$\begingroup$

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

$\endgroup$
2

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.