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 Apr 25 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 at 4:17

Your Answer

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

Browse other questions tagged or ask your own question.