<p>The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know).</p>

<p><a href="https://i.sstatic.net/RVdfa.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/RVdfa.png" alt="enter image description here"></a></p>

<p>Two notes:</p>

<ul>
<li><p>+X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all <em>distinct</em> labels;</p></li>
<li><p>in the figure  each label appears $\leq 2$ times; but it is <em>straightforward</em> to make each label appears <em>exactly 2 times</em> adding some dum nodes+edges+labels to pair them up.</p></li>
</ul>

CC BY-SA 3.0
2016-05-13T15:07:23.700Z
2016-05-14T21:02:34.537Z
2016-05-14T21:02:34.537Z
Marzio De Biasi
<p>Checking if there are two <em>edge-disjoint</em> paths from $s$ to $t$ 
in a given undirected graph $G$ is in P via a standard solution based on maxflow. 
I am interested in the complexity of the following <em>edge-labeled version</em> and
whether it is in P or not.</p>

<p><strong>Input</strong>: An edge-labeled graph $G$ and two vertices $s$ and $t$ satisfying the following condition:</p>

<blockquote>
  <p>every label in $G$ occurs exactly twice.  </p>
</blockquote>

<p><strong>Output</strong>: are there two label-disjoint paths in $G$ from $s$ to $t$?</p>

<p>Two paths are <em>label disjoint</em> iff
the labels appearing in the respective paths are disjoint.</p>

<p><strong>Example</strong>: 
suppose $G$ is given by $(s, a, v1)$, $(v1, b, t)$, $(s, b, v2)$, $(s, c, v2)$, $(v2, a, t)$, $(v2, c, t)$. Then $s-a-v1-b-t$ and $s-c-v2-c-t$ are two label-disjoint simple paths from $s$ to $t$.</p>

<ds.algorithms><graph-theory><graph-algorithms><disjoint-paths>
Label-disjoint paths in directed graphs
user39012
# Label-disjoint paths in directed graphs

(Asked by: username_0 on 2016-05-13)

Checking if there are two *edge-disjoint* paths from $s$ to $t$
in a given undirected graph $G$ is in P via a standard solution based on maxflow.
I am interested in the complexity of the following *edge-labeled version* and
whether it is in P or not.

**Input**: An edge-labeled graph $G$ and two vertices $s$ and $t$ satisfying the following condition:

> every label in $G$ occurs exactly twice.

**Output**: are there two label-disjoint paths in $G$ from $s$ to $t$?

Two paths are *label disjoint* iff
the labels appearing in the respective paths are disjoint.

**Example**:
suppose $G$ is given by $(s, a, v1)$, $(v1, b, t)$, $(s, b, v2)$, $(s, c, v2)$, $(v2, a, t)$, $(v2, c, t)$. Then $s-a-v1-b-t$ and $s-c-v2-c-t$ are two label-disjoint simple paths from $s$ to $t$.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, disjoint-paths

---

## 1 answers

### Answer by username_1 on 2016-05-13. Score: 6 | Accepted answer

The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know).

[![enter image description here](https://i.sstatic.net/RVdfa.png)](https://i.sstatic.net/RVdfa.png)

Two notes:

* +X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all *distinct* labels;
* in the figure each label appears $\leq 2$ times; but it is *straightforward* to make each label appears *exactly 2 times* adding some dum nodes+edges+labels to pair them up.


---

