3
$\begingroup$

I have a question regarding a problem I'm working on.

The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a sink. Each source must be paired to a single sink, and each sink must be paired to a single source, however all of the sources are compatible with all of the sinks. This could be imagined as k identical locks and k identical keys, all that matters is that its possible to move the keys into locks without having paths that intersect. By contrast in the original problem, sink Si must be paired with source Di and this is an input parameter of the problem.

The underlying problem is NP-Hard but according to a vague comment I found, with the given restriction it can be solved in polynomial time. Unfortunately I can't find any relevant literature that could help.

https://stackoverflow.com/questions/19404033/all-pairs-maximally-disjoint-paths-algorithm/19411277#19411277

If anyone could point me towards proofs or papers that discuss this problem I would appreciate it.

$\endgroup$
3
$\begingroup$

Your link refers to edge-disjoint paths -- i.e., vertices can visited by multiple paths, but no edge can be visited by multiple paths. It sounds like you want vertex-disjoint paths -- is that right? Please edit to clarify.

Both problems can be solved in polynomial time with a Maximum Flow algorithm.

For edge-disjoint paths, put unit-capacity bidirectional edges (i.e., one edge in each direction) between every pair of adjacent vertices; make a super-source $s$, with unit-capacity out-edges to each of the $k$ sources, and a super-sink $t$, with unit-capacity in-edges from each of the $k$ sinks. The capacity constraints ensure that no edge is used by more than one path.

For vertex-disjoint paths, do the same -- but then replace every vertex $v$ with two vertices, $v_-$ and $v_+$, with all of $v$'s in-edges incident on $v_-$ and all of $v$'s out-edges incident on $v_+$, and add a single directed edge of unit capacity from $v_-$ to $v_+$.

$\endgroup$
  • $\begingroup$ Yes I should have specified. I had heard about using the max flow but wasnt sure if it was applicable to this type. Thanks $\endgroup$ – inspuration Aug 29 at 22:54
  • $\begingroup$ You're welcome :) $\endgroup$ – j_random_hacker Aug 29 at 23:40
  • $\begingroup$ Btw the graph is undirected, so a node with 4 cardinal neighbours would be transformed into 2 nodes each sharing the same 4 neighbours? Also forgot to mention it is indeed vertex disjoint. $\endgroup$ – inspuration Aug 29 at 23:48
  • $\begingroup$ Even if the original graph is undirected, the graph you create is directed (sorry, that wasn't clear). So the 2 vertices will share the same 4 neighbours, but 1 will have 4 in-edges, the other 4 out-edges. $\endgroup$ – j_random_hacker Aug 30 at 0:44
  • $\begingroup$ Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers! $\endgroup$ – inspuration Aug 30 at 1:08

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.