<p>Given a graph <span class="math-container">$G=(V,E)$</span>, here is a Linear Relaxation of the edge cover polytope:</p>
<p>(1) For each <span class="math-container">$v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$</span></p>
<p>(2) For each <span class="math-container">$e \in E$</span>, <span class="math-container">$0 \leq x_e \leq 1.$</span></p>
<p>Here <span class="math-container">$\delta(S)$</span> is the set of edges with exactly one endpoint in <span class="math-container">$S$</span>.</p>
<p>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.</p>
<p>I am trying to prove the half-integrality on general graphs by using a transformation to a new bipartite graph <span class="math-container">$\tilde G$</span>, obtained from <span class="math-container">$G$</span> by placing a new vertex 'in the middle' of each edge. Note that this makes <span class="math-container">$\tilde G$</span> a bipartite graph.</p>
<p>However, I'm struggling with the details. Given an extreme point of the polytope for <span class="math-container">$G$</span>, I need to somehow create a feasible point for <span class="math-container">$\tilde G$</span>. Then I can apply the integrality and transform it back somehow.</p>
<p>Can anyone help me out with how to proceed?</p>

CC BY-SA 4.0
2021-04-07T12:56:15.090Z
Maybe some ideas from here could help? https://cstheory.stackexchange.com/questions/46964/proof-that-optimal-solutions-of-lp-relaxation-of-independent-set-are-half-integr
Neal Young
CC BY-SA 4.0
2021-04-08T07:25:22.783Z
I actually figured out the answer
Karagounis Z
<graph-theory><co.combinatorics><optimization><linear-programming>
Prove that this linear relaxation has half-integral extreme points
Karagounis Z
# Prove that this linear relaxation has half-integral extreme points

(Asked by: username_0 on 2021-04-06)

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?

**Tags:** graph-theory, co.combinatorics, optimization, linear-programming
> **Comments:**
> **username_1**: Maybe some ideas from here could help? https://cstheory.stackexchange.com/questions/46964/proof-that-optimal-solutions-of-lp-relaxation-of-independent-set-are-half-integr  
> **username_0**: I actually figured out the answer  

---

## 0 answers

