# Label-disjoint paths in directed graphs

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$.

• 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.