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.

|cite|improve this question
$\endgroup$
  • 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$ – Chandra Chekuri Nov 18 '13 at 0:30
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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But it uses Mixed Interger Linear Programming, which is NP-hard... Is it any good? $\endgroup$ – Thomas Ahle Nov 18 '13 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$ – Chandra Chekuri Feb 27 '14 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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