Check if edge is included in SOME MST in linear time (non-distinct values)

Question

I am working on an algorithm to check if a given edge is included in one of all possible mst's.

For this question, we are considering non-distinct values and our edge e connects vertices A & B.

So far, I have: If a path can be made from A to B consisting of edges with weights less than or equal to the weight of our edge e--we can say that edge e is not a part of any MST.

Am I missing anything here/ ideas on a better algorithm?

EDIT:

What are thoughts on a solution involving the cycle property-- So, we consider all edges with weight less than the edge we are considering. If we can make a path from A->B with those edges, we can say that it is not part of any MST?

Morceau

Any ideas on what I should be looking at to solve this? – Morceau

possible duplicate of Find whether a minimum spanning tree contains an edge in linear time? – Tournai

Answer 1

We will solve this using MST cycle property, which says that, "For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of all other edges of C, then this edge cannot belong to an MST."

Now, run the following O(E+V) algorithm to test if the edge E connecting vertices u and v will be a part of some MST or not.

Step 1

Run dfs from one of the end-points(either u or v) of the edge E considering only those edges that have weight less than that of E.

Step 2

Case 1 If at the end of this dfs, the vertices u and v get connected, then edge E cannot be a part of some MST. This is because in this case there definitely exists a cycle in the graph with the edge E having the maximum weight and it cannot be a part of the MST(from the cycle property).

Case 2 But if at the end of the dfs u and v stay disconnected, then edge E must be the part of some MST as in this case E is always not the maximum weight edge in all the cycles that it is a part of.

Biff

Answer 2

I will write down my thoughts about this problem.
The cycle property is very important in here: The largest edge in any cycle can't be in a minimum spanning tree.
To prove the cycle property, suppose that there is a minimum spanning tree T that contains the edge e which is the largest cost edge in a cycle. Then we can delete the edge e in tree T and we get two sets S and T. Then the cycle must contain some edge other than e that connects the sets S and T. Then from the cut property, the edge e can't be in a minimum spanning tree.

Once we have the cycle property, then we go on to make a claim about whether some edge e is in a minimum spanning tree:
The edge e(v,w) doesn't belong to any minimum spanning tree if and only if there is a path from v and w where every edge on this path is smaller than e.

Using the above claim, the algorithm goes as follows:
Delete all the edges greater than or equal to e, now we have the graph G'. Run DFS to check if v and w are connected in G'. If v and w are still connected, then edge e doesn't belong to any minimum spanning tree. If v and w are not connected, then edge e is in some minimum spanning tree.

Spoondrift

Answer 3

If you start from checking the weight of the edges, it would be too hard to achieve your O(n) limitation.

In order to check if one edge should be in the MST, you should instead start from checking if adding this edge to the graph creates a cycle, we all know that MST can't have any cycles.

• If it does, then just to figure out which route of the at least two routes has the less weight. If your edge e has the minimum weight, then it should be in the MST, otherwise it is just an edge that could form a cycle plus is not the best edge to include in the graph.

• If it doesn't, it has to be in the MST unless any later edge coming into play and beat the existing one.

By doing so, you can achieve O(n) time checking if edge is in the MST.

Anyaanyah

For this question, we are also considering situations (non distinct edge values) where multiple MSTs can exist – Morceau

@Morceau Well, point stands, if the weights are equal, then you know it can be in the MST, where you incidentally found another MST. – Anyaanyah

Answer 4

Suppose A-B is your graph and e the only edge. Then e is part of the MST but there is a path A-B that suffices your condition.

Even if you require that e is not part of such a path it is wrong. Just take a graph with two edges e1 and e2 between A and B that have the same weight.

You should also consider a graph A-B-C with an additional edge from A-C where all edges have weight one. No matter which edge you remove you can get a minimal spanning tree. Thus any edge can be part of a MST.

Cadell

Good point--do you have any other ideas on how to solve this? – Morceau

"You should also consider a graph A-B-C with an additional edge from A-C where all edges have weight one. No matter which edge you remove you can get a minimal spanning tree. Thus any edge can be part of a MST." Ok, how can we put together/ alter my algorithm so that it will come to this conclusion? – Morceau