0
$\begingroup$

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?

$\endgroup$
2

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.