<p>I found a replacement path allocation for <span class="math-container">$_$</span> in a more general setting. Consider an edge <span class="math-container">$_1$</span> that uses edge <span class="math-container">$_2$</span> on its path. The allocation induces a dependency from <span class="math-container">$_1$</span> to <span class="math-container">$_2$</span>. Mutual exclusion defined above corresponds to a cycle of 2 such dependencies. Now consider the more general setting: a cycle of <span class="math-container">$$</span> dependencies induced by a path allocation on <span class="math-container">$_$</span>. Assume vertices are <span class="math-container">$0,…,−1$</span>. On edges <span class="math-container">$,$</span>, the path allocation <span class="math-container">$,+1,0,+1,$</span> induces cycles of dependencies no shorter than <span class="math-container">$$</span>. In my application it means that <span class="math-container">$_$</span> can tolerate up to <span class="math-container">$−1$</span> edge failures (i.e. edge removal).</p>

<p>Same problem on hypercubes, published here:
<a href="https://ct.cs.univie.ac.at/research/publications/publication/5837/" rel="nofollow noreferrer">''Local Fast Segment Rerouting on Hypercubes''</a></p>

<p>Further solutions were submitted recently. Will update soon.</p>

CC BY-SA 4.0
2019-05-14T15:25:32.990Z
2019-05-14T15:25:32.990Z
Parham
<p>A <strong>replacement path</strong> is a simple path allocated to an edge $e \in G$
that connects the endpoints of $e$ in $G \setminus \{e\}$.</p>

<p><strong>The problem</strong></p>

<p>An undirected graph $G$ is given and the task is to allocate a replacement path $P_e$ to each edge 
$e \in G$ such that for any pair of edges $e_1$ and $e_2$ it holds:
if $e_2 \in P_{e_1}$ then $e_1 \not\in P_{e_2}$.
In words, no two edges use each other in their replacement path.
I call the paths $P_{e_1}$ and $P_{e_2}$ <strong>mutually exclusive</strong>.</p>

<p>The path length is not bounded and they can share edges. So any path allocation that satisfies the
mutual exclusion would be good.</p>

<p>Now the <strong>question</strong>: is there already any problem closely related to this?</p>

<p>One could reduce this problem to Maximum Independent Sets problem: a vertex for every $(e,P_e)$ and edges connecting conflicting pairs (i.e. pairs violating the ME). However, in order to get a polynomial size instance we need to restrict the model so that each edge gets a constant number of candidate paths.
However, this is not desired because the MIS instances seem to be NP-Hard (or not?).</p>

CC BY-SA 4.0
2018-07-02T13:56:00.403Z
@NealYoung Thanks for your comment! It should be clear now.
Parham
CC BY-SA 4.0
2018-07-04T06:18:16.533Z
Is such a path allocation feasible in any graph? (Any valid example?)
Saeed
CC BY-SA 4.0
2018-07-04T15:20:58.847Z
A necessary condition is that $G$ is 3-edge-connected.  A sufficient condition is that $G$ contains 3 edge-disjoint spanning trees.  I think the latter condition is not necessary, though as $K_4$ does not have 3 edge-disjoint spanning trees, but does admit a set of replacement paths: $P_{ac}=(a,d,c)$, $P_{ad}=(a,b,d)$, $P_{cd}=(c,b,a,d)$, $P_{ab}=(a,c,b)$, $P_{bc}=(c, a, d, b)$, $P_{bd}=(b, a, c, d)$.
Neal Young
CC BY-SA 4.0
2018-07-05T09:28:22.523Z
Good point @NealYoung, I considered k_4 but didn't try it on paper (I thought it is not feasible there).
Saeed
CC BY-SA 4.0
2018-07-05T14:27:41.600Z
Can anybody find an example of a 3-edge connected graph that doesn't admit a set of replacement paths?
Neal Young
<graph-theory><co.combinatorics><disjoint-paths>
Mutually exclusive replacement paths, an existing problem?
Parham
# Mutually exclusive replacement paths, an existing problem?

(Asked by: username_0 on 2018-07-02)

A **replacement path** is a simple path allocated to an edge $e \in G$
that connects the endpoints of $e$ in $G \setminus \{e\}$.

**The problem**

An undirected graph $G$ is given and the task is to allocate a replacement path $P\_e$ to each edge
$e \in G$ such that for any pair of edges $e\_1$ and $e\_2$ it holds:
if $e\_2 \in P\_{e\_1}$ then $e\_1 \not\in P\_{e\_2}$.
In words, no two edges use each other in their replacement path.
I call the paths $P\_{e\_1}$ and $P\_{e\_2}$ **mutually exclusive**.

The path length is not bounded and they can share edges. So any path allocation that satisfies the
mutual exclusion would be good.

Now the **question**: is there already any problem closely related to this?

One could reduce this problem to Maximum Independent Sets problem: a vertex for every $(e,P\_e)$ and edges connecting conflicting pairs (i.e. pairs violating the ME). However, in order to get a polynomial size instance we need to restrict the model so that each edge gets a constant number of candidate paths.
However, this is not desired because the MIS instances seem to be NP-Hard (or not?).

**Tags:** graph-theory, co.combinatorics, disjoint-paths
> **Comments:**
> **username_0**: @NealYoung Thanks for your comment! It should be clear now.  
> **username_1**: Is such a path allocation feasible in any graph? (Any valid example?)  
> **username_2**: A necessary condition is that $G$ is 3-edge-connected.  A sufficient condition is that $G$ contains 3 edge-disjoint spanning trees.  I think the latter condition is not necessary, though as $K_4$ does not have 3 edge-disjoint spanning trees, but does admit a set of replacement paths: $P_{ac}=(a,d,c)$, $P_{ad}=(a,b,d)$, $P_{cd}=(c,b,a,d)$, $P_{ab}=(a,c,b)$, $P_{bc}=(c, a, d, b)$, $P_{bd}=(b, a, c, d)$.  
> **username_1**: Good point @NealYoung, I considered k_4 but didn't try it on paper (I thought it is not feasible there).  
> **username_2**: Can anybody find an example of a 3-edge connected graph that doesn't admit a set of replacement paths?  

---

## 1 answers

### Answer by username_0 on 2019-05-14. Score: 1

I found a replacement path allocation for $\_$ in a more general setting. Consider an edge $\_1$ that uses edge $\_2$ on its path. The allocation induces a dependency from $\_1$ to $\_2$. Mutual exclusion defined above corresponds to a cycle of 2 such dependencies. Now consider the more general setting: a cycle of $$ dependencies induced by a path allocation on $\_$. Assume vertices are $0,…,−1$. On edges $,$, the path allocation $,+1,0,+1,$ induces cycles of dependencies no shorter than $$. In my application it means that $\_$ can tolerate up to $−1$ edge failures (i.e. edge removal).

Same problem on hypercubes, published here:
[''Local Fast Segment Rerouting on Hypercubes''](https://ct.cs.univie.ac.at/research/publications/publication/5837/)

Further solutions were submitted recently. Will update soon.


---

