How do I find the maximum independent set of a bipartite graph via Maximum Network Flow?
Background is in computer science, but I realize I'm well and fully into graph-theory, here.
I have constructed the following bipartite graph where each node represents either a vertical or horizontal chord of a polygon. I construct an edge between the nodes if the two chords intersect or share a vertex.
As I understand it* (and implemented it), the Maximum Flow algorithm can be used to find the Maximum Independent Set in the following manner:
*not guaranteed to be correct, mind!
Convert the bipartite graph into a directed graph, adding a "universal source" and "ultimate sink" node to the graph, to get this:
Next, find a path from Source to Sink (I implemented a Depth-first search). Once you find a valid path, reverse the directions of the edges along the path, and try to find a new path. After all paths from Source -> Sink have been exhausted, the edges of the new graph that go from h -> v form... a matching? (At this point, my knowledge of terminology breaks down).
The iterations of said algorithm (I think this is equivalently the Hungarian Maximum Matching method?) look like this:
Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:
Of which the maximum independent set is one of either pair of nodes, so "v1, v2, v3" would be a maximum independent set, as would "v2, h2, h3".
(I believe for completeness I may also need to add any v or h nodes that do not have any edges other than to Sink or Source).
Long story short, am I way off base here? Am I missing some step or fundamentally misunderstanding how to calculate what I'm looking for? The data I'm comparing against suggests and answer of v2, h2, h3 (or u1, r2, r3 in this diagram), but it also mentions that there are multiple maximally independent sets that are equivalent, just with different nodes.
Anyway, am I way off-base here? I feel like I'm 90% of the way there, and I'm just not fully grasping how to go from (b) to (c). Any help? (Or at least a start pointing me in the appropriate direction to know how I can learn more relevant graph stuff!)
graph-theory bipartite-graph network-flow
asked Nov 24 at 3:58
Raven Dreamer
1871210
add a comment |
Background is in computer science, but I realize I'm well and fully into graph-theory, here.
I have constructed the following bipartite graph where each node represents either a vertical or horizontal chord of a polygon. I construct an edge between the nodes if the two chords intersect or share a vertex.
As I understand it* (and implemented it), the Maximum Flow algorithm can be used to find the Maximum Independent Set in the following manner:
*not guaranteed to be correct, mind!
Convert the bipartite graph into a directed graph, adding a "universal source" and "ultimate sink" node to the graph, to get this:
Next, find a path from Source to Sink (I implemented a Depth-first search). Once you find a valid path, reverse the directions of the edges along the path, and try to find a new path. After all paths from Source -> Sink have been exhausted, the edges of the new graph that go from h -> v form... a matching? (At this point, my knowledge of terminology breaks down).
The iterations of said algorithm (I think this is equivalently the Hungarian Maximum Matching method?) look like this:
Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:
Of which the maximum independent set is one of either pair of nodes, so "v1, v2, v3" would be a maximum independent set, as would "v2, h2, h3".
(I believe for completeness I may also need to add any v or h nodes that do not have any edges other than to Sink or Source).
Long story short, am I way off base here? Am I missing some step or fundamentally misunderstanding how to calculate what I'm looking for? The data I'm comparing against suggests and answer of v2, h2, h3 (or u1, r2, r3 in this diagram), but it also mentions that there are multiple maximally independent sets that are equivalent, just with different nodes.
Anyway, am I way off-base here? I feel like I'm 90% of the way there, and I'm just not fully grasping how to go from (b) to (c). Any help? (Or at least a start pointing me in the appropriate direction to know how I can learn more relevant graph stuff!)
graph-theory bipartite-graph network-flow
asked Nov 24 at 3:58
Raven Dreamer
1871210
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36
add a comment |
Background is in computer science, but I realize I'm well and fully into graph-theory, here.
I have constructed the following bipartite graph where each node represents either a vertical or horizontal chord of a polygon. I construct an edge between the nodes if the two chords intersect or share a vertex.
As I understand it* (and implemented it), the Maximum Flow algorithm can be used to find the Maximum Independent Set in the following manner:
*not guaranteed to be correct, mind!
Convert the bipartite graph into a directed graph, adding a "universal source" and "ultimate sink" node to the graph, to get this:
Next, find a path from Source to Sink (I implemented a Depth-first search). Once you find a valid path, reverse the directions of the edges along the path, and try to find a new path. After all paths from Source -> Sink have been exhausted, the edges of the new graph that go from h -> v form... a matching? (At this point, my knowledge of terminology breaks down).
The iterations of said algorithm (I think this is equivalently the Hungarian Maximum Matching method?) look like this:
Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:
Of which the maximum independent set is one of either pair of nodes, so "v1, v2, v3" would be a maximum independent set, as would "v2, h2, h3".
(I believe for completeness I may also need to add any v or h nodes that do not have any edges other than to Sink or Source).
Long story short, am I way off base here? Am I missing some step or fundamentally misunderstanding how to calculate what I'm looking for? The data I'm comparing against suggests and answer of v2, h2, h3 (or u1, r2, r3 in this diagram), but it also mentions that there are multiple maximally independent sets that are equivalent, just with different nodes.
Anyway, am I way off-base here? I feel like I'm 90% of the way there, and I'm just not fully grasping how to go from (b) to (c). Any help? (Or at least a start pointing me in the appropriate direction to know how I can learn more relevant graph stuff!)
graph-theory bipartite-graph network-flow
asked Nov 24 at 3:58
Raven Dreamer
1871210
Background is in computer science, but I realize I'm well and fully into graph-theory, here.
I have constructed the following bipartite graph where each node represents either a vertical or horizontal chord of a polygon. I construct an edge between the nodes if the two chords intersect or share a vertex.
As I understand it* (and implemented it), the Maximum Flow algorithm can be used to find the Maximum Independent Set in the following manner:
*not guaranteed to be correct, mind!
Convert the bipartite graph into a directed graph, adding a "universal source" and "ultimate sink" node to the graph, to get this:
Next, find a path from Source to Sink (I implemented a Depth-first search). Once you find a valid path, reverse the directions of the edges along the path, and try to find a new path. After all paths from Source -> Sink have been exhausted, the edges of the new graph that go from h -> v form... a matching? (At this point, my knowledge of terminology breaks down).
The iterations of said algorithm (I think this is equivalently the Hungarian Maximum Matching method?) look like this:
Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:
Of which the maximum independent set is one of either pair of nodes, so "v1, v2, v3" would be a maximum independent set, as would "v2, h2, h3".
(I believe for completeness I may also need to add any v or h nodes that do not have any edges other than to Sink or Source).
Long story short, am I way off base here? Am I missing some step or fundamentally misunderstanding how to calculate what I'm looking for? The data I'm comparing against suggests and answer of v2, h2, h3 (or u1, r2, r3 in this diagram), but it also mentions that there are multiple maximally independent sets that are equivalent, just with different nodes.
Anyway, am I way off-base here? I feel like I'm 90% of the way there, and I'm just not fully grasping how to go from (b) to (c). Any help? (Or at least a start pointing me in the appropriate direction to know how I can learn more relevant graph stuff!)
graph-theory bipartite-graph network-flow
graph-theory bipartite-graph network-flow
asked Nov 24 at 3:58
Raven Dreamer
1871210
asked Nov 24 at 3:58
Raven Dreamer
1871210
asked Nov 24 at 3:58
Raven Dreamer
1871210
asked Nov 24 at 3:58
Raven Dreamer
1871210
asked Nov 24 at 3:58
Raven Dreamer
1871210
1871210
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36
add a comment |
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f3011165%2fhow-do-i-find-the-maximum-independent-set-of-a-bipartite-graph-via-maximum-netwo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmath.stackexchange.com%2fquestions%2f3011165%2fhow-do-i-find-the-maximum-independent-set-of-a-bipartite-graph-via-maximum-netwo%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
cs.stackexchange.com/q/3027
– Jean Marie
Nov 24 at 5:06
Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches.
– Jean Marie
Nov 24 at 5:12
@JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser.
– Raven Dreamer
Nov 24 at 5:20
Thanks for the reference.
– Jean Marie
Nov 24 at 5:25
The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
– Jean Marie
Nov 24 at 5:36