7

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

Mario Giambarioli
  • 203
  • 2
  • 8
  • 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 04:17

1 Answers1

5

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.

SimonT
  • 701
  • 5
  • 8
  • 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 09:07
  • I add the constraints of two disjoint circles of length 3. – SimonT Dec 20 '20 at 09: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 09:21