3
$\begingroup$

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?).

$\endgroup$
  • $\begingroup$ @NealYoung Thanks for your comment! It should be clear now. $\endgroup$ – Parham Jul 2 '18 at 13:56
  • $\begingroup$ Is such a path allocation feasible in any graph? (Any valid example?) $\endgroup$ – Saeed Jul 4 '18 at 6:18
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Neal Young Jul 4 '18 at 15:20
  • $\begingroup$ Good point @NealYoung, I considered k_4 but didn't try it on paper (I thought it is not feasible there). $\endgroup$ – Saeed Jul 5 '18 at 9:28
  • 1
    $\begingroup$ Can anybody find an example of a 3-edge connected graph that doesn't admit a set of replacement paths? $\endgroup$ – Neal Young Jul 5 '18 at 14:27
1
$\begingroup$

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''

Further solutions were submitted recently. Will update soon.

$\endgroup$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.