4
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ See arxiv.org/abs/1310.2378 and 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. $\endgroup$ Commented Nov 18, 2013 at 0:30
  • $\begingroup$ Did you ended up finding any good solutions? $\endgroup$ Commented May 26, 2023 at 5:38

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But it uses Mixed Interger Linear Programming, which is NP-hard... Is it any good? $\endgroup$ Commented Nov 18, 2013 at 20:15
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 27, 2014 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.