# Minimum vertex cover and linear programming

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.

We find a half integral optimal solution of LP that we call $$S_{hi}$$. For each variable $$x_{i}$$ that takes value 0 in $$S_{hi}$$, we add the constraint $$x_{i}=0$$ to LP.

For each odd cycle of G, add to LP the constraint $$x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$$ where $$x_{a},x_{b},x_{c},...,x_{i}$$ are the vertices of the cycle and $$k$$ is the number of vertices of the cycle. We find a new optimal solution of LP that we call $$S$$.

If $$x_{i}$$ is a variable that takes value $$0.5$$ in $$S_{hi}$$ and value $$\gt 0.5$$ in $$S$$, can we say that there is at least a minimum vertex cover of G that contains the vertex associated to $$x_{i}$$?

• Could you motivate us why you think the hypothesis in your question may be true? – batwing Apr 25 '20 at 18:35
• @batwing In an odd cycle c with $k$ vertices, the number of vertices needed to cover the cycle is $\frac{1}{2}(k+1)$, therefore for each odd cycle we add to LP the constraint $x_{a}+x_{b}+x_{c}+...+x_{i}\geq \frac{1}{2}(k+1)$. If in $S_{hi}$ the sum of the variable of c is $\frac{k}{2}$ (that is all the variables of c take value $\frac{1}{2}$), then in $S$ at least a variable $x_{i}$ of c takes vale $\gt \frac{1}{2}$ and the vertex associated to $x_{i}$ belongs to at least a minimum vertex cover of the given graph. – Mario Giambarioli Apr 26 '20 at 4:17

I am pretty sure the answer is NO!

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

The optimal LP relaxation $$S_{hi}$$ is taking all nodes with value $$\frac{1}{2}$$.

Adding the extra odd circle constraints one can get an optimal solution $$S$$ by setting all nodes to $$\frac{2}{3}$$. Optimality can be seen by the following argument. For each of the seven nodes $$v_i$$ add two circle constraints that cover the remaining six nodes together, which gives a new constraint $$\sum_{j\neq i}x_j\geq 4$$. Adding all of these scaled by $$\frac{1}{6}$$ gives the new inequality $$\sum_{i}x_i\geq 4\cdot \frac{7}{6}$$, which proofs optimality of the solution where all nodes get value $$\frac{2}{3}$$. Thus each of the nodes would fulfil your condition.

But the only optimal vertex cover consists of all the nodes in the $$K_5$$ leaving the two nodes $$r_1, r_2$$ out.

• SimoT, you are right when you say “one can get an optimal solution by setting all nodes to $\frac{2}{3}$”, but when you say “as the smallest odd circles have length $3$” it is wrong. In fact, suppose we have two circles: $c_{1}$ with $3$ nodes and $c_{2}$ with $5$ nodes and $c_{1}$ $c_{2}$ have only one node in common that we say $a$. In this example we have an optimal solution when all the nodes, except $a$, take $\frac{1}{2}$ and the node $a$ takes $1$. If all the nodes take value $\frac{2}{3}$ ($c_{1}$ is the smallest odd circle and it has $3$ nodes) we do not have an optimal solution. – Mario Giambarioli Dec 19 '20 at 13:09
• You are absolutely right! I added a proper proof now. – SimonT Dec 19 '20 at 14:26
• SimonT, I am sorry but I do not understand why you add the constraint $\sum\limits_{j\neq i}{x_{j}} \geq 4$, I think it should be $\sum\limits_{j\neq i}{x_{j}} \geq 3$ because they are even circles (they have $6$ nodes). Then you say to scale by $\frac{1}{6}$ but you write $4\cdot \frac{7}{6}$. – Mario Giambarioli Dec 20 '20 at 9:07
• I add the constraints of two disjoint circles of length 3. – SimonT Dec 20 '20 at 9:20
• And it's seven constraints I get from this. One for each node. But as each node only appears in six of them adding all scaled by 1/6 gives exactly the sum over all nodes ones. – SimonT Dec 20 '20 at 9:21