Delete k vertices from a graph such that it remains connected
$begingroup$
Given an undirected graph G(V,E) where each V has an integer value, remove k number of vertices such that there is a path between all the remaining vertices and the sum of the remaining values are maximal. In other words, remove k vertices with the lowest sum of values. Solution must be optimal.
I am wondering what algorithm I can use for this. I am thinking of backtracking.
graph-theory
asked Dec 8 '18 at 11:26
user3022069user3022069
133
$endgroup$
add a comment |
$begingroup$
Given an undirected graph G(V,E) where each V has an integer value, remove k number of vertices such that there is a path between all the remaining vertices and the sum of the remaining values are maximal. In other words, remove k vertices with the lowest sum of values. Solution must be optimal.
I am wondering what algorithm I can use for this. I am thinking of backtracking.
graph-theory
asked Dec 8 '18 at 11:26
user3022069user3022069
133
$endgroup$
$begingroup$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
1
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
1
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22
add a comment |
$begingroup$
Given an undirected graph G(V,E) where each V has an integer value, remove k number of vertices such that there is a path between all the remaining vertices and the sum of the remaining values are maximal. In other words, remove k vertices with the lowest sum of values. Solution must be optimal.
I am wondering what algorithm I can use for this. I am thinking of backtracking.
graph-theory
asked Dec 8 '18 at 11:26
user3022069user3022069
133
$endgroup$
Given an undirected graph G(V,E) where each V has an integer value, remove k number of vertices such that there is a path between all the remaining vertices and the sum of the remaining values are maximal. In other words, remove k vertices with the lowest sum of values. Solution must be optimal.
I am wondering what algorithm I can use for this. I am thinking of backtracking.
graph-theory
graph-theory
asked Dec 8 '18 at 11:26
user3022069user3022069
133
asked Dec 8 '18 at 11:26
user3022069user3022069
133
edited Dec 8 '18 at 11:33
user3022069
asked Dec 8 '18 at 11:26
user3022069user3022069
133
asked Dec 8 '18 at 11:26
user3022069user3022069
133
asked Dec 8 '18 at 11:26
user3022069user3022069
133
133
$begingroup$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
1
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
1
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22
add a comment |
$begingroup$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
1
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
1
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22
$begingroup$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
$begingroup$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
1
1
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
1
1
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
$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
});
}
});
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%2f3030984%2fdelete-k-vertices-from-a-graph-such-that-it-remains-connected%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$
If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
$endgroup$
add a comment |
$begingroup$
If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
$endgroup$
add a comment |
$begingroup$
If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
$endgroup$
If the graph is a grid with $2$ rows and $N$ columns, then a dynamic programming approach should work.
The idea is to compute recursively the answers to questions similar to the following one: considering only the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices?
There is a problem, however, if you try to answer recursively the questions exactly as stated above. I'm not writing the details here, but you will have troubles keeping track of the connectedness of the set of vertices you are choosing. The tecnique to get around this kind of problems is to make the questions more precise adding restrictions (consequently you will have to consider a larger number of questions). In this specific case you should consider in addition questions like the following: in the subgraph given by the first $n$ columns, what is the maximum sum you can get adding the values of $q$ distinct connected vertices, with the restriction that you have to include the upper (or lower) vertex in the $n-$th column?
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
answered Dec 8 '18 at 22:08
Francesco MiliziaFrancesco Milizia
564
564
add a comment |
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%2f3030984%2fdelete-k-vertices-from-a-graph-such-that-it-remains-connected%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$
At the first glance the problem seems to be hard. Maybe even $NP$-hard. Can you provide a bit of the problem context?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 11:54
1
$begingroup$
This graph is created from a 2*N matrix. Each cell in the matrix is represented by a vertex with a value and each edge is represented by the upper and horizontal neighbourhood. So no diagonal edges.
$endgroup$
– user3022069
Dec 8 '18 at 12:08
$begingroup$
So the graph is actually a $2times n$ grid, right?
$endgroup$
– Alex Ravsky
Dec 8 '18 at 12:17
1
$begingroup$
Basically, yes.
$endgroup$
– user3022069
Dec 8 '18 at 12:22