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


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

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.


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.