Mixing
Check MST validity given a graph with intervals as edges costs
I literally bashed my head trying to figure this question.
Given an undirected and connected graph G , all the edges in G have unknown costs but it is known the interval of each cost for each edge for example the cost of edge e is in the closed interval [i,j] where i and j are real numbers. I am also given a spanning tree of G named T. I need to create an algorithm to check if T can be a minimum spanning tree of G or not.
I tried connecting this problem to network flow but I could not reach a solution. Is there any a hint for finding a solution to a problem like this?
algorithm minimum-spanning-tree
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
add a comment |
I literally bashed my head trying to figure this question.
Given an undirected and connected graph G , all the edges in G have unknown costs but it is known the interval of each cost for each edge for example the cost of edge e is in the closed interval [i,j] where i and j are real numbers. I am also given a spanning tree of G named T. I need to create an algorithm to check if T can be a minimum spanning tree of G or not.
I tried connecting this problem to network flow but I could not reach a solution. Is there any a hint for finding a solution to a problem like this?
algorithm minimum-spanning-tree
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
1
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14
add a comment |
I literally bashed my head trying to figure this question.
Given an undirected and connected graph G , all the edges in G have unknown costs but it is known the interval of each cost for each edge for example the cost of edge e is in the closed interval [i,j] where i and j are real numbers. I am also given a spanning tree of G named T. I need to create an algorithm to check if T can be a minimum spanning tree of G or not.
I tried connecting this problem to network flow but I could not reach a solution. Is there any a hint for finding a solution to a problem like this?
algorithm minimum-spanning-tree
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
I literally bashed my head trying to figure this question.
Given an undirected and connected graph G , all the edges in G have unknown costs but it is known the interval of each cost for each edge for example the cost of edge e is in the closed interval [i,j] where i and j are real numbers. I am also given a spanning tree of G named T. I need to create an algorithm to check if T can be a minimum spanning tree of G or not.
I tried connecting this problem to network flow but I could not reach a solution. Is there any a hint for finding a solution to a problem like this?
algorithm minimum-spanning-tree
algorithm minimum-spanning-tree
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
edited Dec 31 '18 at 17:14
shadi helf
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
asked Dec 31 '18 at 16:15
shadi helfshadi helf
164
164
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
1
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14
add a comment |
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
1
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
1
1
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14
add a comment |
1 Answer
1
active
oldest
votes
This problem can be solved using linear programming. Checking if T can be a minimum spanning tree amounts to checking the feasibility of a set of linear constraints on a set of |E| variables, one for each edge of the graph. The variable x(u,v) corresponds to the weight of the edge (u,v). That is, a feasible solution to the linear program is an assignment of weights to the graph edges such that T is a minimum spanning tree. So, for a start, each variable x(u,v) is constrained to be within the specified interval.
The other constraints, which I'll specify shortly, are designed to be satisfied if and only if T is a minimum spanning tree under the assignment that solves the program.
To understand why under every assignment that satisfies the following constraints T must be a minimum spanning tree, you have to convince yourself of the following property of minimum spanning trees:
A spanning tree T is a minimum spanning tree if and only if for every edge (u,v) not in T and every edge e in the path from u to v in T, w(u,v)>=w(e). This property follows from the cut property.
So, to check if T can be a minimum spanning tree, one should check the feasibility of the linear program defined by the following set of constraints.
- For each edge in the graph,
i(u,v)<=x(u,v)<=j(u,v). - For each edge
(u,v)not in T and each edgeein the path fromutovin T,x(u,v)>=x(e).
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53989405%2fcheck-mst-validity-given-a-graph-with-intervals-as-edges-costs%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
This problem can be solved using linear programming. Checking if T can be a minimum spanning tree amounts to checking the feasibility of a set of linear constraints on a set of |E| variables, one for each edge of the graph. The variable x(u,v) corresponds to the weight of the edge (u,v). That is, a feasible solution to the linear program is an assignment of weights to the graph edges such that T is a minimum spanning tree. So, for a start, each variable x(u,v) is constrained to be within the specified interval.
The other constraints, which I'll specify shortly, are designed to be satisfied if and only if T is a minimum spanning tree under the assignment that solves the program.
To understand why under every assignment that satisfies the following constraints T must be a minimum spanning tree, you have to convince yourself of the following property of minimum spanning trees:
A spanning tree T is a minimum spanning tree if and only if for every edge (u,v) not in T and every edge e in the path from u to v in T, w(u,v)>=w(e). This property follows from the cut property.
So, to check if T can be a minimum spanning tree, one should check the feasibility of the linear program defined by the following set of constraints.
- For each edge in the graph,
i(u,v)<=x(u,v)<=j(u,v). - For each edge
(u,v)not in T and each edgeein the path fromutovin T,x(u,v)>=x(e).
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
add a comment |
This problem can be solved using linear programming. Checking if T can be a minimum spanning tree amounts to checking the feasibility of a set of linear constraints on a set of |E| variables, one for each edge of the graph. The variable x(u,v) corresponds to the weight of the edge (u,v). That is, a feasible solution to the linear program is an assignment of weights to the graph edges such that T is a minimum spanning tree. So, for a start, each variable x(u,v) is constrained to be within the specified interval.
The other constraints, which I'll specify shortly, are designed to be satisfied if and only if T is a minimum spanning tree under the assignment that solves the program.
To understand why under every assignment that satisfies the following constraints T must be a minimum spanning tree, you have to convince yourself of the following property of minimum spanning trees:
A spanning tree T is a minimum spanning tree if and only if for every edge (u,v) not in T and every edge e in the path from u to v in T, w(u,v)>=w(e). This property follows from the cut property.
So, to check if T can be a minimum spanning tree, one should check the feasibility of the linear program defined by the following set of constraints.
- For each edge in the graph,
i(u,v)<=x(u,v)<=j(u,v). - For each edge
(u,v)not in T and each edgeein the path fromutovin T,x(u,v)>=x(e).
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
add a comment |
This problem can be solved using linear programming. Checking if T can be a minimum spanning tree amounts to checking the feasibility of a set of linear constraints on a set of |E| variables, one for each edge of the graph. The variable x(u,v) corresponds to the weight of the edge (u,v). That is, a feasible solution to the linear program is an assignment of weights to the graph edges such that T is a minimum spanning tree. So, for a start, each variable x(u,v) is constrained to be within the specified interval.
The other constraints, which I'll specify shortly, are designed to be satisfied if and only if T is a minimum spanning tree under the assignment that solves the program.
To understand why under every assignment that satisfies the following constraints T must be a minimum spanning tree, you have to convince yourself of the following property of minimum spanning trees:
A spanning tree T is a minimum spanning tree if and only if for every edge (u,v) not in T and every edge e in the path from u to v in T, w(u,v)>=w(e). This property follows from the cut property.
So, to check if T can be a minimum spanning tree, one should check the feasibility of the linear program defined by the following set of constraints.
- For each edge in the graph,
i(u,v)<=x(u,v)<=j(u,v). - For each edge
(u,v)not in T and each edgeein the path fromutovin T,x(u,v)>=x(e).
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
This problem can be solved using linear programming. Checking if T can be a minimum spanning tree amounts to checking the feasibility of a set of linear constraints on a set of |E| variables, one for each edge of the graph. The variable x(u,v) corresponds to the weight of the edge (u,v). That is, a feasible solution to the linear program is an assignment of weights to the graph edges such that T is a minimum spanning tree. So, for a start, each variable x(u,v) is constrained to be within the specified interval.
The other constraints, which I'll specify shortly, are designed to be satisfied if and only if T is a minimum spanning tree under the assignment that solves the program.
To understand why under every assignment that satisfies the following constraints T must be a minimum spanning tree, you have to convince yourself of the following property of minimum spanning trees:
A spanning tree T is a minimum spanning tree if and only if for every edge (u,v) not in T and every edge e in the path from u to v in T, w(u,v)>=w(e). This property follows from the cut property.
So, to check if T can be a minimum spanning tree, one should check the feasibility of the linear program defined by the following set of constraints.
- For each edge in the graph,
i(u,v)<=x(u,v)<=j(u,v). - For each edge
(u,v)not in T and each edgeein the path fromutovin T,x(u,v)>=x(e).
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
edited Jan 1 at 23:21
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
answered Jan 1 at 21:12
snakilesnakile
24.8k49140211
24.8k49140211
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
add a comment |
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
Thanks for the hint I think I got the answer now
– shadi helf
Jan 2 at 1:03
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f53989405%2fcheck-mst-validity-given-a-graph-with-intervals-as-edges-costs%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
You must be skipping some details. Because the problem you mentioned is unsolvable. There are plenty of intervals for which a spanning tree can be both minimum or not depending on the actual values of the edges.
– merlyn
Dec 31 '18 at 16:57
This is the question. There are no missing details
– shadi helf
Dec 31 '18 at 17:14
Then the problem is unsolvable. Consider nodes a, b & c all connected to one another with edges each in interval [1, 10]. If T contains a-b & b-c, is it MST? Answer: Depends on the actual values of the edges a-b, b-c & c-a.
– merlyn
Dec 31 '18 at 18:18
1
@merlyn I think the question is if it's possible that (with the right assignments of edge costs) the given treen is a minimum spanning tree, not whether it is. In your example, if the intervals for all three edges were identical, then any tree of two edges can be an MST. At least that's the way I read it.
– beaker
Jan 1 at 17:14