Finding missing two edges in a MST in O(m) time

Question

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with n-3 edges, representing some minimum spanning tree as a list.

I've tried using standard greedy algorithms but they would require checking for a cycle which makes it larger than O(m). Is there any way to check if a particular edge is the right one without the need of checking for cycles?

Answer 1

There are a few observations one can make:

• Graph $T$ consists of three components (allowing the possibility of one-vertex components) which are not connected to each other. In order to turn it into a spanning tree, we need to add two edges, each of them joining one pair of components.
• Total weight of the spanning tree is the weight of $T$ (which is beyond our control) plus the weight of the two added edges. Clearly, it only makes sense to join two components using edge of the least weight; any other would be sub-optimal.
• This leaves us with three edges to consider as candidates for adding to $T$; so finding which pair is optimal becomes trivial.

These observations can be turned into an algorithm:

1. Identify the components of $T$ by simple depth-first search over its edges. There are just $O(n)$ edges in $T$, so the whole process runs in $O(n)$ time.
2. Iterate over all edges of $G$, look only at those whose ends belong to different components and keep track of the edge of the least weight for each pair of components. There are $O(m)$ edges to be considered, so the processing takes $O(m)$ time.
3. From the three edges found in previous step, get rid of one with the greatest weight. $O(1)$ time.

Since $m\geq (n-1)$, total processing time is $O(m)$.