Find whether a minimum spanning tree contains an edge in linear time?

Question

I have the following problem on my homework:

Give an O(n+m) algorithm to find that whether an edge e would be a part of the MST of a graph

(We are allowed to get help from others on this assignment, so this isn't cheating.)

I think that I could do a BFS and find if this edge is a edge between two layers and if so whether this edge was the smallest across those layers. But what could I say when this edge is not a tree edge of the BFS tree?

Discoloration

Answer 1

As a hint, if an edge is not the heaviest edge in any cycle that contains it, there is some MST that contains that edge. To see this, consider any MST. If the MST already contains the edge, great! We're done. If not, then add the edge into the MST. This creates a cycle in the graph. Now, find the heaviest edge in that cycle and remove it from the graph. Everything is now still connected (because if two nodes used to be connected by a path that went across that edge, now they can be connected by just going around the cycle the other way). Moreover, since the cost of the edge was deleted wasn't any smaller than the cost of the edge in question (because the edge isn't the heaviest edge in the cycle), the cost of this tree can't be any greater than before. Since we started with an MST, we must therefore end with an MST.

Using this property, see if you can find whether the edge is the heaviest edge on any cycle in linear time.

Googol

Shorter version: what does Kruskal's algorithm need to decide whether edge e is included? – Somebody

@Googol Dont you think edge E will in the MST only when it is not the heaviest edge of all the cycles that it is a part of(rather than "if an edge is not the heaviest edge in some cycle"). For example see this pastebin.com/irVzKXJa – Rockwell

Answer 2

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 never the maximum weight edge of the cycles that it is a part of.

Rockwell

Answer 3

Find if there are any paths that are cheaper than the current one (u,v) that creates a cycle to u and v. If yes, then (u,v) is not on the mst. Otherwise it is. This can be proved by the cut property and the cycle property.

Coadjutrix