# Practical algorithms for the disjoint paths problem

Given an undirected graph $G$ and two pairs of vertices $(s_1, t_1), (s_2, t_2)$, the disjoint paths problem (DPP) asks for two vertex-disjoint paths, one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$.

The problem has been shown to be in $P$ even for the generalization with $k$ disjoint paths, where $k$ is a constant [1, 2].

I'm interested in practical algorithms to solve this problem. The algorithm given in [1] runs in $\mathcal{O}(nm)$ but uses many case distinctions which makes it very cumbersome to implement.

Are there any known algorithms which are more practical to implement, even at the expense of a worse runtime guarantee?

I'm interested in application to 3D grid graphs, so results assuming planarity or low tree-width unfortunately do not help.

• Some special cases where there are easier-to-implement algorithms: (a) where $s_1=s_2$ and $t_1=t_2$ (then it's network flow), (b) the graph is a DAG (then there are dedicated algorithms, based on the product construction: the product of the graph with itself). If your problem happens to fall into one of these two special cases, do let us know, as then I can suggest some simpler algorithms. – D.W. Jun 17 '15 at 6:12
• Unfortunately I'm interested in the case where $s_1 \not = s_2$ and $t_1 \not = t_2$ and my graph is undirected and in general non-planar. However, thank you for your contribution! – Elrond1337 Jun 17 '15 at 7:37