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

  • $\begingroup$ When you set $x_i=0$, all the variables of the adjacent vertices of $v_{x_{i}}$ take value $1$. $\endgroup$ Aug 6, 2020 at 12:56
  • $\begingroup$ 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. $\endgroup$ Aug 6, 2020 at 13:05

1 Answer 1


Consider the graph

 /  |\ /|
1   | × |
 \  |/ \|

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.


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.