Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope:

(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$

(2) For each $e \in E$, $0 \leq x_e \leq 1.$

Here $\delta(S)$ is the set of edges with exactly one endpoint in $S$.

It is known that the above polyhedron has integral extreme points when G is a bipartite graph. It is also known that, in a general graph, any extreme point of the polyhedron is half-integral - that is, it's coordinates are either integers or multiples of 1/2.

I am trying to prove the half-integrality on general graphs by using a transformation to a new bipartite graph $\tilde G$, obtained from $G$ by placing a new vertex 'in the middle' of each edge. Note that this makes $\tilde G$ a bipartite graph.

However, I'm struggling with the details. Given an extreme point of the polytope for $G$, I need to somehow create a feasible point for $\tilde G$. Then I can apply the integrality and transform it back somehow.

Can anyone help me out with how to proceed?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.