How to create sets of nodes on a colored graph while cutting as few edges as possible
$begingroup$
I'm a programmer not a mathematician so my jargon is terrible and I apologize.
My problem:
I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of the same color (probably not relevant). I now want to create sets of nodes such that it contains exactly one node of each color. I want to select every set such that in the end there are as few edges that cross between sets as possible.
Solution?:
All I can think of is the obvious approach of partitioning it into sets randomly then iterating through every node and testing every swap from its current set into another set and then counting whether this increases or decreases the number of edge exits. Then when you find the best swap you make the swap. You then repeat until you find no swaps that improve the edge exit count.
Now 1. How do I prove that this will in fact find the optimum solution and not a "local optimum" and 2. How can this be done more efficiently.
I'm sure it's a solved problem already but I don't know how to google for it because it's been so long since I've studied things like this. Any guidance would be very helpful. Thank you.
graph-theory algorithms computer-science set-partition
asked Dec 8 '18 at 2:58
colwemcolwem
62
$endgroup$
add a comment |
$begingroup$
I'm a programmer not a mathematician so my jargon is terrible and I apologize.
My problem:
I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of the same color (probably not relevant). I now want to create sets of nodes such that it contains exactly one node of each color. I want to select every set such that in the end there are as few edges that cross between sets as possible.
Solution?:
All I can think of is the obvious approach of partitioning it into sets randomly then iterating through every node and testing every swap from its current set into another set and then counting whether this increases or decreases the number of edge exits. Then when you find the best swap you make the swap. You then repeat until you find no swaps that improve the edge exit count.
Now 1. How do I prove that this will in fact find the optimum solution and not a "local optimum" and 2. How can this be done more efficiently.
I'm sure it's a solved problem already but I don't know how to google for it because it's been so long since I've studied things like this. Any guidance would be very helpful. Thank you.
graph-theory algorithms computer-science set-partition
asked Dec 8 '18 at 2:58
colwemcolwem
62
$endgroup$
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01
add a comment |
$begingroup$
I'm a programmer not a mathematician so my jargon is terrible and I apologize.
My problem:
I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of the same color (probably not relevant). I now want to create sets of nodes such that it contains exactly one node of each color. I want to select every set such that in the end there are as few edges that cross between sets as possible.
Solution?:
All I can think of is the obvious approach of partitioning it into sets randomly then iterating through every node and testing every swap from its current set into another set and then counting whether this increases or decreases the number of edge exits. Then when you find the best swap you make the swap. You then repeat until you find no swaps that improve the edge exit count.
Now 1. How do I prove that this will in fact find the optimum solution and not a "local optimum" and 2. How can this be done more efficiently.
I'm sure it's a solved problem already but I don't know how to google for it because it's been so long since I've studied things like this. Any guidance would be very helpful. Thank you.
graph-theory algorithms computer-science set-partition
asked Dec 8 '18 at 2:58
colwemcolwem
62
$endgroup$
I'm a programmer not a mathematician so my jargon is terrible and I apologize.
My problem:
I have a graph (relatively sparse) and I've colored all its nodes. There are no edges between nodes of the same color (probably not relevant). I now want to create sets of nodes such that it contains exactly one node of each color. I want to select every set such that in the end there are as few edges that cross between sets as possible.
Solution?:
All I can think of is the obvious approach of partitioning it into sets randomly then iterating through every node and testing every swap from its current set into another set and then counting whether this increases or decreases the number of edge exits. Then when you find the best swap you make the swap. You then repeat until you find no swaps that improve the edge exit count.
Now 1. How do I prove that this will in fact find the optimum solution and not a "local optimum" and 2. How can this be done more efficiently.
I'm sure it's a solved problem already but I don't know how to google for it because it's been so long since I've studied things like this. Any guidance would be very helpful. Thank you.
graph-theory algorithms computer-science set-partition
graph-theory algorithms computer-science set-partition
asked Dec 8 '18 at 2:58
colwemcolwem
62
asked Dec 8 '18 at 2:58
colwemcolwem
62
edited Dec 8 '18 at 3:26
colwem
asked Dec 8 '18 at 2:58
colwemcolwem
62
asked Dec 8 '18 at 2:58
colwemcolwem
62
asked Dec 8 '18 at 2:58
colwemcolwem
62
62
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01
add a comment |
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:
- There are only three colors,
- There are $q$ vertices (the same number) of each color,
- We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.
Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.
This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.
Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
$endgroup$
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
add a comment |
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%2f3030650%2fhow-to-create-sets-of-nodes-on-a-colored-graph-while-cutting-as-few-edges-as-pos%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$
Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:
- There are only three colors,
- There are $q$ vertices (the same number) of each color,
- We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.
Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.
This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.
Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
$endgroup$
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
add a comment |
$begingroup$
Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:
- There are only three colors,
- There are $q$ vertices (the same number) of each color,
- We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.
Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.
This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.
Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
$endgroup$
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
add a comment |
$begingroup$
Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:
- There are only three colors,
- There are $q$ vertices (the same number) of each color,
- We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.
Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.
This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.
Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
$endgroup$
Solving this problem is NP-complete (and therefore no polynomial-time solution is known), even in the special case where:
- There are only three colors,
- There are $q$ vertices (the same number) of each color,
- We only want to know if the theoretical minimum of edges that cross between sets is possible: $m-3q$, where $m$ is the total number of edges in the graph $G$.
Equivalently, we want to know if it's possible to choose $q$ triples such that each triple forms a triangle in $G$.
This is the PARTITION INTO TRIANGLES problem, which is NP-complete, as shown for instance here, or for an even more specialized case as Proposition 5.1 here.
Solving the problem in more general cases is likely to be even harder. It's possible, however, that a good approximation algorithm exists, which gets close to the minimum number of edges that cross between sets.
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
answered Dec 8 '18 at 17:47
Misha LavrovMisha Lavrov
45.1k656107
45.1k656107
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
add a comment |
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
Ok, I read the first one. the second one is quite long and I'm kind of exhausted from the first. In that one he proves the NP-completeness by constructing a graph for which partitioning into triangles must be NP-complete. However it does not show that PT on all graphs are NP-complete. In addition the graph he constructs is pretty specific, maybe most graphs aren't like that. Could we come up with properties of the graph that would make PT polynomial time. Also, thank you very much for your help.
$endgroup$
– colwem
Dec 8 '18 at 21:48
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
$begingroup$
"It does not show that PT on all graphs are NP-complete" - this is how NP-completeness proofs work in general. If you construct one kind of graph for which a problem is hard, then this is enough to rule out an algorithm for which all cases are easy. As for coming up with properties of the graph that would make the problem polynomial time - well, for instance, if we only had $2$ colors and not $3$, then your problem would just be a maximum-matching problem, which is relatively easy.
$endgroup$
– Misha Lavrov
Dec 8 '18 at 22:02
add a comment |
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.
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%2f3030650%2fhow-to-create-sets-of-nodes-on-a-colored-graph-while-cutting-as-few-edges-as-pos%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
$begingroup$
I'm not sure I follow all the constraints. Are there the same number of nodes of each color? Let's call a set with exactly one node of each color a "rainbow set." Am I right in assuming that the rainbow sets must be disjoint? And that you want to have the maximum number of rainbow sets?
$endgroup$
– saulspatz
Dec 8 '18 at 4:16
$begingroup$
Yes to all. Maybe there won't be the same number of nodes of each color but for right now we can just assume there are and so you can put every node in a disjoint rainbow set.
$endgroup$
– colwem
Dec 8 '18 at 16:01