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}$?

  • $\begingroup$ Could you motivate us why you think the hypothesis in your question may be true? $\endgroup$
    – batwing
    Commented Apr 25, 2020 at 18:35
  • $\begingroup$ @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. $\endgroup$ Commented Apr 26, 2020 at 4:17

1 Answer 1


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

counter example

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.

  • $\begingroup$ 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. $\endgroup$ Commented Dec 19, 2020 at 13:09
  • $\begingroup$ You are absolutely right! I added a proper proof now. $\endgroup$
    – SimonT
    Commented Dec 19, 2020 at 14:26
  • $\begingroup$ 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}$. $\endgroup$ Commented Dec 20, 2020 at 9:07
  • $\begingroup$ I add the constraints of two disjoint circles of length 3. $\endgroup$
    – SimonT
    Commented Dec 20, 2020 at 9:20
  • $\begingroup$ 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. $\endgroup$
    – SimonT
    Commented Dec 20, 2020 at 9:21

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.