Minimum vertex cover and linear programming 2

Question

This is a modified version of the algorithm that I have proposed here.

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.

Consider the following algorithm:

1. Find an optimal solution $S$ of LP.

2. For each variable $x_{i}$, one by one, add the constraint $x_{i}=0$ to LP and find a new optimal solution $S’$. If in $S’$ the objective function is greater than in $S$, remove the constraint $x_{i}=0$.

3. Find an optimal solution $S’’$ of LP. Remove all the vertices from $G$ that take value $0$ or $1$ in $S’’$.

4. For each odd cycle $C$ in $G$, add the constraint $x_{a}+x_{b}+x_{c}+...+x_{i}\geq \left\lfloor h+1 \right\rfloor$ where $x_{a},x_{b},x_{c},...,x_{i}$ are the vertices of the cycle and $h$ is the sum of the values of the variables of $C$ in $S’’$.

5. If any constraints are added in the step 4., repeat from 2..

6. The vertices whose variables take value $1$ in $S’’$ are a minimum vertex cover of the given $G$.

The algorithm finds a vertex cover of the given graph, this is clear. The question is: does the algorithm find a minimum vertex cover of the given graph?

The idea behind the algorithm is: in a graph without odd cycles, the optimal value of the objective function of LP is the cardinality of the minimum vertex cover of the given graph (1). If there are any odd cycles, the optimal value of the objective can be less than the cardinality of the minimum vertex cover. For this reason, the algorithm increases the lower limit of the sum of the variables of each odd cycle of $G$, until all the variables take value in $\left\{0, 1\right\} $ in $S’’$.

(1) G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Mathematical Programming, 6:48–61, 1974.

Answer 1

I am pretty sure the answer is again NO. And it can be seen with the same graph as in the previous question here.

Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $K_5$.

First note that if we force any of the nodes $r_1, r_2$ to take value $0$ in any of the LP formulations all the nodes in $K_5$ have to take value $1$ in order to cover all the edges from $K_5$ to the respective $r_1, r_2$. Thus an optimal LP solution would at least take value $5$. Furthermore if we force any of the nodes in $K_5$ to take value $0$ then all the other nodes have to take value $1$, as each node in $K_5$ is connected to all other nodes and these edges have to be covered. Thus an optimal LP solution would at least take value $6$.

As was shown in the original answer the first optimal LP solution we find gives all nodes value $\frac{1}{2}$. As seen above step 2 will not add any additional constraints and step 3 will not remove anything. Then the constraints added in step 4 are exactly the ones from the previous question.

So as shown in the original answer the next optimal solution found will assign all nodes value $\frac{2}{3}$. Again with the argument from above step 2 and 3 will not do anything. Now step 4 will add constraints that will force all cycles of length $3$ to take at least value $3$.

As each node is contained in a cycle of length $3$ this implies that the next solution found has to take all vertices with value $1$. Now forcing any of the nodes to value $0$ will make the solution illegal, as the respective new cycle constraints are violated. Thus the algorithm terminates with a solution that has value $7$, where the optimal solution would be $5$.