8

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.

[1]: Shiloach, Y. (1980). A polynomial solution to the undirected two paths problem. Journal of the ACM (JACM), 27(3), 445-456.

[2]: Robertson, N., & Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1), 65-110.

David Richerby
  • 81,689
  • 26
  • 141
  • 235
Elrond1337
  • 81
  • 1
  • 1
    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 06: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 07:37

0 Answers0