# Minimum vertex cover and linear programming

Suppose we have a graph G. Consider the minimum vertex cover problem of G formulated as a linear programming problem, that is for each vertex $$v_{i}$$ we have the variable $$x_{i}$$, for each edge $$v_{i}v_{j}$$ we have the constraint $$x_{i}+x_{j}\geq 1$$, for each variable we have $$0\leq x_{i}\leq 1$$ and we have the objective function $$\min \sum\limits_{1}^{n}{x_{i}}$$. We call such a linear programming problem LP. Note that it is NOT an integer linear programming problem.

We find a half integral optimal solution of LP that we call $$S_{hi}$$. For each variable $$x_{i}$$ that takes value 0 in $$S_{hi}$$, we add the constraint $$x_{i}=0$$ to LP.

For each odd cycle of G, add to LP the constraint $$x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$$ where $$x_{a},x_{b},x_{c},...,x_{i}$$ are the vertices of the cycle and $$k$$ is the number of vertices of the cycle. We find a new optimal solution of LP that we call $$S$$.

If $$x_{i}$$ is a variable that takes value $$0.5$$ in $$S_{hi}$$ and value $$\gt 0.5$$ in $$S$$, can we say that there is at least a minimum vertex cover of G that contains the vertex associated to $$x_{i}$$?

• Could you motivate us why you think the hypothesis in your question may be true? – batwing Apr 25 at 18:35
• @batwing In an odd cycle c with $k$ vertices, the number of vertices needed to cover the cycle is $\frac{1}{2}(k+1)$, therefore for each odd cycle we add to LP the constraint $x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$. If in $S_{hi}$ the sum of the variable of c is $\frac{k}{2}$ (that is all the variables of c take value $\frac{1}{2}$), then in $S$ at least a variable $x_{i}$ of c takes vale $\gt \frac{1}{2}$ and the vertex associated to $x_{i}$ belongs to at least a minimum vertex cover of the given graph. – Mario Giambarioli Apr 26 at 4:17