# Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $$G$$ with $$n$$ vertices, set up a linear programming problem LP where there is a variable $$x_i$$ for each vertex $$v_i$$ of $$G$$, each variable can take value $$\geq 0$$, for each edge $$v_av_b$$ of $$G$$ set the constraint $$x_a+x_b\geq 1$$. The objective function is $$\min\sum\limits_{1}^{n}{x_i}$$. Find the variable (or one of the variables) $$x_i$$, among the variables not set to $$0$$, that set to $$0$$ gives the minimum value of the objective function. Add the constraint $$x_i=0$$ to LP. Repeat until the optimal solution of LP is integer (that is each variable takes value in $$\left\{0; 1\right\}$$).

I am looking for a graph where the vertices associated to the variables that take value $$1$$ in the final optimal solution of LP are not a minimum vertex cover of $$G$$ (if it exists).

• When you set $x_i=0$, all the variables of the adjacent vertices of $v_{x_{i}}$ take value $1$. – Mario Giambarioli Aug 6 at 12:56
• The algorithm set to $0$ a variable that does not take value $0$ in $S$. Anyway my description of the algoritm is not clear. I am going to modify it. Thank you for your help. – Mario Giambarioli Aug 6 at 13:05

  2-4---7

Setting $$x_1,x_2,x_3,x_6$$ or $$x_7$$ to 0 gives your LP a value of 4, while setting $$x_4$$ or $$x_5$$ to 0 gives your LP a value of 5. However, if you set $$x_1=0$$, you will finally get a vertex cover of size 5, while the optimal vertex cover is of size 4.