8
$\begingroup$

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

Improve this question
$\endgroup$
  • $\begingroup$ Could you motivate us why you think the hypothesis in your question may be true? $\endgroup$ – batwing Apr 25 '20 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$ – Mario Giambarioli Apr 26 '20 at 4:17
5
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\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$ – Mario Giambarioli Dec 19 '20 at 13:09
  • $\begingroup$ You are absolutely right! I added a proper proof now. $\endgroup$ – SimonT Dec 19 '20 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$ – Mario Giambarioli Dec 20 '20 at 9:07
  • $\begingroup$ I add the constraints of two disjoint circles of length 3. $\endgroup$ – SimonT Dec 20 '20 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 Dec 20 '20 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.