<p>It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.</p>
<p>Here is a Linear Relaxation of the edge cover polytope, which I am trying to show is integral:</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">$S \subseteq V, |S|$</span> is odd, <span class="math-container">$\sum_{e \in E[S] \cup \delta(S)} x_e \geq \frac{|S| + 1}{2}.$</span></p>
<p>(3) 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> - note that this includes self-loops on vertices in <span class="math-container">$S$</span>. However, <span class="math-container">$E[S]$</span> does not count self-loops. With these definitions it can be shown that these inequalities are valid for the edge cover polytope.</p>
<p>To show this, my goal is to reduce this problem to the integrality of the edge cover polytope on simple graphs.</p>
<p>Here is my idea: given a graph <span class="math-container">$G$</span> which may have self-loops, we construct a doubled graph <span class="math-container">$\tilde G$</span> which has two copies of the nodes in <span class="math-container">$G$</span>. Also, if <span class="math-container">$v$</span> had a self-loop in <span class="math-container">$G$</span>, then we put a &quot;bridge&quot; edge <span class="math-container">$e = (v,v')$</span> between the two copies of vertex <span class="math-container">$v$</span> in <span class="math-container">$\tilde G$</span>.</p>
<p>I want to say that given an edge cover <span class="math-container">$x$</span> in <span class="math-container">$G$</span>, it can be made into an edge cover <span class="math-container">$\tilde x$</span> in <span class="math-container">$\tilde G$</span> by duplicating the graph, and putting the value of the self-loops onto the bridges. But does <span class="math-container">$\tilde x$</span> satisfy all the odd set constraints for <span class="math-container">$\tilde G$</span>? In some sense my problem reduces to the following:</p>
<p>In <span class="math-container">$\tilde G$</span> suppose that <span class="math-container">$\tilde x$</span> satisfies all odd sets <span class="math-container">$S$</span> which lie on ONE SIDE of the graph. Then can we show that actually all odd set constraints are satisfied?</p>

CC BY-SA 4.0
2020-07-24T14:33:12.317Z
Here's another possible approach.  Fix any feasible solution $x$. Obtain $x'$ from $x$ as follows.  For any self-loop $e=(v,v)$ such that $x_{v,v}\in (0,1)$, there must be another edge $(v, w)$ on $v$.  Set $x'_{v,v}=0$ and $x'_{v, w}=\min(1, x_{v, w} + x_{v, v})$.  For all edges not set in this way, set $x'_{v, w} = x_{v, w}$.  Then $x'$ is an equally good solution, isn't it?  And $x'_{v,v} \in \{0,1\}$ for every self-loop...
Neal Young
CC BY-SA 4.0
2020-07-24T21:45:05.750Z
Your new point $x'$ will indeed be feasible, and since the self-loops are integral it can be written as a convex combination of integral edge covers. 
But how can we then write $x$ as a convex combination of edge covers? There is no reverse transformation since making an edge into a self-loop may break its other endpoint.
Karagounis Z
CC BY-SA 4.0
2020-07-25T01:49:27.010Z
Good point. I was arguing that there is no integrality gap if the objective is to minimize $\sum_e x_e$, but this does not show that the polytope is integral.
Neal Young
CC BY-SA 4.0
2020-07-25T01:50:08.590Z
So how about this attempt?  Given $G$, add two new vertices $u$ and $w$ and an edge $(u,w)$, then replace every self-loop $(v, v)$ by an edge $(v, w)$.  Call the resulting graph $G'$.  It has no self loops.  Maybe (?) the feasible solutions $x$ for $G$ correspond bijectively to the feasible solutions $x'$ for $G'$, and the bijection preserves integrality.  The proposed bijection is to take $x'_{uw} = 1$ (which is forced by $u$) and $x'_{vw} = x_{vv}$ for all self-loops $(v, v)$, and $x'_e = x_e$ for other edges.
Neal Young
CC BY-SA 4.0
2020-07-25T01:51:50.167Z
BTW do you also have constraints $0\le x_e \le 1$?
Neal Young
CC BY-SA 4.0
2020-07-25T18:14:18.820Z
Your approach does work. It can be checked that the new point $x'$ is feasible in the new graph by casework on how many dummy vertices the odd set contains. If you are curious I can write this down. Also I'm not sure how to accept your answer if its a comment.
I'm still wondering about the question I posed though. The transformation in my question preserves more of the structure of the graph
Karagounis Z
CC BY-SA 4.0
2020-07-25T20:22:46.753Z
@KaragounisZ You could post it (with some of the details that you figured out) as an answer and self-accept it if you want.  Or if you prefer I can post it as a (very brief) answer.
Neal Young
CC BY-SA 4.0
2020-08-22T11:47:59.533Z
Sorry for my lack of knowledge, but what is the edge cover polytope, or what is an edge cover?
Yixin Cao
<graph-theory><linear-programming><integer-programming><polytope>
Is the edge cover polytope integral on graphs with self-loops?
Karagounis Z
# Is the edge cover polytope integral on graphs with self-loops?

(Asked by: username_0 on 2020-07-24)

It is well known that the edge cover polytope is integral on simple graphs. I am wondering whether this also holds for graphs with self-loops.

Here is a Linear Relaxation of the edge cover polytope, which I am trying to show is integral:

(1) For each $v \in V, \sum\_{e \in \delta(v)} x\_e \geq 1.$

(2) For each $S \subseteq V, |S|$ is odd, $\sum\_{e \in E[S] \cup \delta(S)} x\_e \geq \frac{|S| + 1}{2}.$

(3) 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$ - note that this includes self-loops on vertices in $S$. However, $E[S]$ does not count self-loops. With these definitions it can be shown that these inequalities are valid for the edge cover polytope.

To show this, my goal is to reduce this problem to the integrality of the edge cover polytope on simple graphs.

Here is my idea: given a graph $G$ which may have self-loops, we construct a doubled graph $\tilde G$ which has two copies of the nodes in $G$. Also, if $v$ had a self-loop in $G$, then we put a "bridge" edge $e = (v,v')$ between the two copies of vertex $v$ in $\tilde G$.

I want to say that given an edge cover $x$ in $G$, it can be made into an edge cover $\tilde x$ in $\tilde G$ by duplicating the graph, and putting the value of the self-loops onto the bridges. But does $\tilde x$ satisfy all the odd set constraints for $\tilde G$? In some sense my problem reduces to the following:

In $\tilde G$ suppose that $\tilde x$ satisfies all odd sets $S$ which lie on ONE SIDE of the graph. Then can we show that actually all odd set constraints are satisfied?

**Tags:** graph-theory, linear-programming, integer-programming, polytope

> **Comments:**
> **username_1**: Here's another possible approach.  Fix any feasible solution $x$. Obtain $x'$ from $x$ as follows.  For any self-loop $e=(v,v)$ such that $x_{v,v}\in (0,1)$, there must be another edge $(v, w)$ on $v$.  Set $x'_{v,v}=0$ and $x'_{v, w}=\min(1, x_{v, w} + x_{v, v})$.  For all edges not set in this way, set $x'_{v, w} = x_{v, w}$.  Then $x'$ is an equally good solution, isn't it?  And $x'_{v,v} \in \{0,1\}$ for every self-loop...  
> **username_0**: Your new point $x'$ will indeed be feasible, and since the self-loops are integral it can be written as a convex combination of integral edge covers.  But how can we then write $x$ as a convex combination of edge covers? There is no reverse transformation since making an edge into a self-loop may break its other endpoint.  
> **username_1**: Good point. I was arguing that there is no integrality gap if the objective is to minimize $\sum_e x_e$, but this does not show that the polytope is integral.  
> **username_1**: So how about this attempt?  Given $G$, add two new vertices $u$ and $w$ and an edge $(u,w)$, then replace every self-loop $(v, v)$ by an edge $(v, w)$.  Call the resulting graph $G'$.  It has no self loops.  Maybe (?) the feasible solutions $x$ for $G$ correspond bijectively to the feasible solutions $x'$ for $G'$, and the bijection preserves integrality.  The proposed bijection is to take $x'_{uw} = 1$ (which is forced by $u$) and $x'_{vw} = x_{vv}$ for all self-loops $(v, v)$, and $x'_e = x_e$ for other edges.  
> **username_1**: BTW do you also have constraints $0\le x_e \le 1$?  
> **username_0**: Your approach does work. It can be checked that the new point $x'$ is feasible in the new graph by casework on how many dummy vertices the odd set contains. If you are curious I can write this down. Also I'm not sure how to accept your answer if its a comment. I'm still wondering about the question I posed though. The transformation in my question preserves more of the structure of the graph  
> **username_1**: @KaragounisZ You could post it (with some of the details that you figured out) as an answer and self-accept it if you want.  Or if you prefer I can post it as a (very brief) answer.  
> **username_2**: Sorry for my lack of knowledge, but what is the edge cover polytope, or what is an edge cover?  

---

## 0 answers

