<p>If you want an implementation, Sage has one. With a LP, as usual ;-)</p>

<p><a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths" rel="nofollow">http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths</a></p>

<p>Nathann</p>

CC BY-SA 3.0
2013-11-18T20:15:36.740Z
But it uses Mixed Interger Linear Programming, which is NP-hard... Is it any good?
Thomas Ahle
CC BY-SA 3.0
2014-02-27T17:30:47.747Z
Many times the LP-based methods give good solutions in a reasonable amount of time if the instances are "easy". You should try them out.
Chandra Chekuri
CC BY-SA 3.0
2013-11-18T16:15:01.877Z
2013-11-18T16:15:01.877Z
Nathann Cohen
<p>I'm looking into the Undirected Vertex Disjoint Paths problem:</p>

<blockquote>
  <p>Given a list of tuples of vertices (s_i, t_i)</p>
  
  <p>Find simple, pairwise disjoint paths P_{s_0,t_0}, P_{s_1,t_1}, ... that connects the given vertices. If they exist.</p>
</blockquote>

<p>I'm in particular interesting in implementing a solution to this this for grid meshes. A situation that comes up in many pen+paper puzzles. I know this will be NP hard in the list of tuples, but hopefully not in the size of the graph.</p>

<p>I know about the Robertson-Seymour theorem, and its complications. However I'm wondering if the required minors might be well known for say planar graphs or meshes?</p>

<p>I also found mentions that Schrijver has made a more approachable polynomial algorithm, but I haven't been able to find mentions of complexity in terms of implementation.</p>

<p>Can anyone point me in a good direction?
I'd be interested even in solutions for just two pairs. </p>

CC BY-SA 3.0
2013-11-18T00:30:39.870Z
See http://arxiv.org/abs/1310.2378 and http://arxiv.org/abs/1304.4207 for two recent "theory" papers on planar disjoint paths. They will have pointers to previous ones. I don't know any references to implementations and would be happy to see some pointers.
Chandra Chekuri
CC BY-SA 4.0
2023-05-26T05:38:53.603Z
Did you ended up finding any good solutions?
Siyuan Zhao
<graph-algorithms><implementation>
Implementations of Undirected Disjoint Paths
Thomas Ahle
# Implementations of Undirected Disjoint Paths

(Asked by: username_0 on 2013-11-17)

I'm looking into the Undirected Vertex Disjoint Paths problem:

> Given a list of tuples of vertices (s\_i, t\_i)
>
> Find simple, pairwise disjoint paths P\_{s\_0,t\_0}, P\_{s\_1,t\_1}, ... that connects the given vertices. If they exist.

I'm in particular interesting in implementing a solution to this this for grid meshes. A situation that comes up in many pen+paper puzzles. I know this will be NP hard in the list of tuples, but hopefully not in the size of the graph.

I know about the Robertson-Seymour theorem, and its complications. However I'm wondering if the required minors might be well known for say planar graphs or meshes?

I also found mentions that Schrijver has made a more approachable polynomial algorithm, but I haven't been able to find mentions of complexity in terms of implementation.

Can anyone point me in a good direction?
I'd be interested even in solutions for just two pairs.

**Tags:** graph-algorithms, implementation

> **Comments:**
> **username_1**: See http://arxiv.org/abs/1310.2378 and http://arxiv.org/abs/1304.4207 for two recent "theory" papers on planar disjoint paths. They will have pointers to previous ones. I don't know any references to implementations and would be happy to see some pointers.  
> **username_2**: Did you ended up finding any good solutions?  

---

## 1 answers

### Answer by username_3 on 2013-11-18. Score: 2

If you want an implementation, Sage has one. With a LP, as usual ;-)

<http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.disjoint_routed_paths>

Nathann

> **Comments:**
> **username_0**: But it uses Mixed Interger Linear Programming, which is NP-hard... Is it any good?  
> **username_1**: Many times the LP-based methods give good solutions in a reasonable amount of time if the instances are "easy". You should try them out.  

---

