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.
