# Finding 2 paths between 2 source-target pairs

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.