Minimum vertex cover algorithm with linear programming

Question

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

• Mario Giambarioli: When you set $x_i=0,ドル all the variables of the adjacent vertices of $v_{x_{i}}$ take value 1ドル$.
• Mario Giambarioli: 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.

Answer 1

Consider the graph

 2-4---7
 / |\ /|
1 | ×ばつ |
 \ |/ \|
 3-5---6

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.