TransWikia.com

Is the edge cover polytope integral on graphs with self-loops?

Theoretical Computer Science Asked on December 24, 2021

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?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP