patternMinor
k-disjoint pair paths where any source can pair with any sink
Viewed 0 times
cansourcewithwherepathsanysinkdisjointpair
Problem
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.
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.
Solution
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_+$.
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_+$.
Context
StackExchange Computer Science Q#113210, answer score: 3
Revisions (0)
No revisions yet.