3
$\begingroup$

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

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.