k-disjoint pair paths where any source can pair with any sinkFinding small node sets that can not be avoided on paths from source to sinkComputing the k shortest edge-disjoint paths on a weighted graphDijkstra's algorithm to compute shortest paths using k edges?Flaw in linear programming solution for multi-commodity flow problem?Algorithm: Shortest path (walk) with keys and doorsoptimal flow for index multiple source and destination in directed graph
How can I fix cracks between the bathtub and the wall surround?
Could a complex system of reaction wheels be used to propel a spacecraft?
Did the Apollo Guidance Computer really use 60% of the world's ICs in 1963?
Fixing a blind bolt hole when the first 2-3 threads are ruined?
Does Dovescape counter Enchantment Creatures?
Defending Castle from Zombies
Wrong Stamping of UK Visa
Is this position a forced win for Black after move 14?
Why does Sauron not permit his followers to use his name?
Give Lightning Web Component a Prettier Name
What is this "opened" cube called?
Group by consecutive index numbers
Do universities maintain secret textbooks?
Why do motor drives have multiple bus capacitors of small value capacitance instead of a single bus capacitor of large value?
I feel cheated by my new employer, does this sound right?
Was it illegal to blaspheme God in Antioch in 360.-410.?
What are ways to record who took the pictures if a camera is used by multiple people
Why didn't Doc believe Marty was from the future?
Can two aircraft be allowed to stay on the same runway at the same time?
Did ancient peoples ever hide their treasure behind puzzles?
Is it possible for a person to be tricked into becoming a lich?
Is the Amazon rainforest the "world's lungs"?
Why military weather satellites?
Don't look at what I did there
k-disjoint pair paths where any source can pair with any sink
Finding small node sets that can not be avoided on paths from source to sinkComputing the k shortest edge-disjoint paths on a weighted graphDijkstra's algorithm to compute shortest paths using k edges?Flaw in linear programming solution for multi-commodity flow problem?Algorithm: Shortest path (walk) with keys and doorsoptimal flow for index multiple source and destination in directed graph
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$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.
algorithms graphs graph-theory
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$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.
algorithms graphs graph-theory
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$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.
algorithms graphs graph-theory
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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.
algorithms graphs graph-theory
algorithms graphs graph-theory
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 5 hours ago
inspuration
asked 9 hours ago
inspurationinspuration
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
inspurationinspuration
163 bronze badges
asked 9 hours ago
inspurationinspuration
163 bronze badges
163 bronze badges
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
inspuration is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$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_+$.
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
inspuration is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f113210%2fk-disjoint-pair-paths-where-any-source-can-pair-with-any-sink%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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_+$.
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
add a comment |
$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_+$.
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
add a comment |
$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_+$.
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
$endgroup$
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_+$.
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
answered 7 hours ago
j_random_hackerj_random_hacker
3,1421 gold badge11 silver badges16 bronze badges
3,1421 gold badge11 silver badges16 bronze badges
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
add a comment |
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
$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
6 hours ago
$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
6 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$begingroup$
You're welcome :)
$endgroup$
– j_random_hacker
5 hours ago
$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
5 hours ago
$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
5 hours ago
$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
4 hours ago
$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
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
$begingroup$
Thank you, that is exactly what I was imagining. I should be good to start writing the actual code now, cheers!
$endgroup$
– inspuration
4 hours ago
add a comment |
inspuration is a new contributor. Be nice, and check out our Code of Conduct.
inspuration is a new contributor. Be nice, and check out our Code of Conduct.
inspuration is a new contributor. Be nice, and check out our Code of Conduct.
inspuration is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f113210%2fk-disjoint-pair-paths-where-any-source-can-pair-with-any-sink%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
