Minimal amount of edges needed to be removed to make a graph triangle free (approximation algorithm)
0
$begingroup$
Given a graph G = (V,E) there is a minimal number of edges - k - that need to be removed to make G triangle free. I'm trying to find an approximation algorithm (that is as efficient as possible) that finds a set of edges to remove to make G triangle free that is no larger than 3k.
Can someone help me?
graph-theory
asked Aug 17 '18 at 8:24
DanDan
31
$endgroup$
|
show 1 more comment
0
$begingroup$
Given a graph G = (V,E) there is a minimal number of edges - k - that need to be removed to make G triangle free. I'm trying to find an approximation algorithm (that is as efficient as possible) that finds a set of edges to remove to make G triangle free that is no larger than 3k.
Can someone help me?
graph-theory
asked Aug 17 '18 at 8:24
DanDan
31
$endgroup$
$begingroup$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59
|
show 1 more comment
0
0
0
$begingroup$
Given a graph G = (V,E) there is a minimal number of edges - k - that need to be removed to make G triangle free. I'm trying to find an approximation algorithm (that is as efficient as possible) that finds a set of edges to remove to make G triangle free that is no larger than 3k.
Can someone help me?
graph-theory
asked Aug 17 '18 at 8:24
DanDan
31
$endgroup$
Given a graph G = (V,E) there is a minimal number of edges - k - that need to be removed to make G triangle free. I'm trying to find an approximation algorithm (that is as efficient as possible) that finds a set of edges to remove to make G triangle free that is no larger than 3k.
Can someone help me?
graph-theory
graph-theory
asked Aug 17 '18 at 8:24
DanDan
31
asked Aug 17 '18 at 8:24
DanDan
31
asked Aug 17 '18 at 8:24
DanDan
31
asked Aug 17 '18 at 8:24
DanDan
31
asked Aug 17 '18 at 8:24
DanDan
31
31
$begingroup$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59
|
show 1 more comment
$begingroup$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59
$begingroup$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59
|
show 1 more comment
1 Answer
1
active
oldest
votes
0
$begingroup$
Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
$endgroup$
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
});
}
});
draft saved
draft discarded
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%2f2885536%2fminimal-amount-of-edges-needed-to-be-removed-to-make-a-graph-triangle-free-appr%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
0
$begingroup$
Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
$endgroup$
add a comment |
0
$begingroup$
Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
$endgroup$
add a comment |
0
0
0
$begingroup$
Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
$endgroup$
Try the greedy algorithm: in each step, eliminate the biggest possible number of triangles by deleting the edge contained in the most triangles.
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
answered Aug 17 '18 at 9:04
A. PongráczA. Pongrácz
5,9531929
5,9531929
add a comment |
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f2885536%2fminimal-amount-of-edges-needed-to-be-removed-to-make-a-graph-triangle-free-appr%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$
Could you show us your efforts? Did you try the greedy algorithm, for example?
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:31
$begingroup$
By greedy algorithm I assume you mean looping through all possible triangles on the graph and removing edges from them as they come. But that won't work. for example you can have a single edge that is part of n-2 triangles (where n is the numbers of vertices) but instead of removing that edge the algorithm will remove n-2 other edges.
$endgroup$
– Dan
Aug 17 '18 at 8:37
$begingroup$
No, my greedy approach would be to compute the number of triangles containing the edge $e$ for all $ein E$. Then pick the edge that is contained in the biggest number of triangles. Remove it. Iterate. Not sure this works, just asking if you tried it.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:39
$begingroup$
So "greedy" is meant in the sense that in each step we eliminate as many triangles as possible.
$endgroup$
– A. Pongrácz
Aug 17 '18 at 8:45
$begingroup$
yes, that seems to work, thanks
$endgroup$
– Dan
Aug 17 '18 at 8:59