1
$\begingroup$

Given an undirected graph $G=(V,E)$ and 2 sources $s_1,s_2$ and 2 targets $t_1,t_2$, I am looking to find paths $P_1$ and $P_2$, where $P_i$ is a path from $s_i$ to $t_i$ and $P_1$ and $P_2$ are edge-disjoint.

One attempt is to find $P_1$ by DFS or BFS, and then find $P_2$ using a DFS/BFS with the remaining edges. Obviously, a solution found by this approach is a valid solution, but we may skip many valid solutions.

Another approach is by using integral flow. Adding a special source vertex and a special target vertex, and capacities of $1$ on the edges. But using this approach, one could get a path $s_1 \rightarrow t_2$ and $s_2 \rightarrow t_1$.

I get a feeling this problem might be NP-Hard, but even if it is, I'm looking for some heuristic approach or some approximation.

$\endgroup$

1 Answer 1

2
$\begingroup$

The problem is known as the Edge disjoint path problem. It can be solved in polynomial time on undirected graphs.

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