What edges are not in any MST?

Question

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.

Answer 1

A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, here is my solution to the question.

Let $G$ be a weighted undirected (finite) graph. An edge $e$ is called superheavy if it is the unique heaviest edge in some cycle. Here is a characterization of the edges that are not in any MST.

An edge is not in any MST if and only if it is a superheavy edge

The well-known "if" part, a superheavy edge is not in any MST, is proved in the cycle property of MST.

The "only if" part, any edge $e$ that is not superheavy is in some MST, is harder to prove. Let me introduce an algorithm and a lemma first.

The delete-heaviest-edge algorithm (DHE) on $G$ removes a heaviest edge in any cycle until no cycle remains. Just to be extra clear, there might be multiple heaviest edges in one cycle. The edge removed can be chosen to be any one of them.

Lemma: DHE is an MST algorithm. That is, the final graph at the end of DHE is an MST of the original $G$.

One proof of the lemma can be developed by adapting the proof at reverse-delete algorithm.

For another proof of the lemma, reader can check my post at the delete-heaviest-edge algorithm on graphs with edges of distinct weights, where I proved the special case where all weights are distinct. For the general case of a given run of DHE where all weights of $G$ are not necessarily distinct, we can perturb the weights of all edges of $G$ so that all weights are distinct and that each edge removed is the unique heaviest edge in the corresponding cycle. We can then repeat the given run of DHE on the perturbed $G$, resulting in the same spanning tree, which is also the MST of the perturbed $G$, since this is the proven special case of distinct weights. By making the perturbation arbitrarily small, we can see the total weight of the resulting MST can be arbitrarily near to the weight of a (or any) MST of the original $G$. Once we take the limit of perturbation going to $0$, we can see that original given run of the DHE must produce a spanning tree with the minimal weight. The lemma is proved.

Now let us prove the "only if" part. Suppose edge $e$ is not a superheavy edge. Let us start a particular run of DHE. We will adjust that run whenever necessary to avoid deleting $e$. Suppose $e$, as a heaviest edge in some cycle is removed in some step. Because $e$ is not superheavy, there is another heaviest edge, say $f$, in that cycle. Let us modify that step so that it removes $f$ instead of $e$. Continue to run the algorithm, alway avoiding removing $e$ as we just did. At the end of the algorithm, we must arrive at an MST thanks to the lemma, which contains $e$. Proof of the "only if" part is done.

Since an edge not in any MST means it is superheavy, any algorithm that finds all the superheavy edges will also finds all edges that are not in any MST.

Algorithms to find all superheavy edges

Here is a naive algorithm. Iterate over all edges. For each edge $e$, pick arbitrarily one of its two vertices. Starting from this chosen vertex, make a DFS or BFS along edges with weight lower than that of $e$, checking whether we have reached the other vertex of $e$ all along. Once we have, $e$ is superheavy. Otherwise we cannot at the end of the search, implying $e$ is not superheavy.

---

It often happens that there is a unique MST, for example when all edge-weights are distinct. We can use various algorithms such as Kruskal's algorithm or Prim's algorithm to compute that unique MST. The superheavy edges are the edges that are not in that unique MST.

---

Here is the efficient algorithm to find all superheavy edges in general cases. Its time-complexity is about the time-complexity to sort the edges by weights, or $O(m\log m + n)$, where $n$ is the number of vertices and $m$ is the number of edges. Its space-complexity is about $O(m+n)$.

1. Sort all edges in groups of increasing weights so that we have $$E=E_1\cup E_2\cup \cdots \cup E_r$$ and $$w_1<w_2<\cdots<w_r,$$ where $E$ is the edge set of $G$ and every edge in $E_i$ has weight $w_i$.
2. Let $H$ be a graph that has the same vertices as $G$ but without any edges. Track the connected components of $H$ by a disjoint-set data structure.
3. For $i$ from 2 to $r$ do the following.
   1. Add all edges in $E_{i-1}$ to $H$.
   2. For each edge in $E_i$, check whether its endpoints are in the same connected component of $H$. If yes, it is a superheavy edge.

Answer 2

The harder part seems to be finding the superlight edges. Isura Manchanayake has provided a good implementation for determining other and superheavy edges. However, using the bridge processor which is effectively a depth first search to do an optimized strongly connected components algorithm, makes this $O(m^2+mn)$ considering a worst case where there are $m$ edge groups, adding one node each time since DFS is $m+n$. It might be constructive to also consider how to optimally discover the superlight edges.

Kruskal's algorithm of course generates an MST and superlight edges have to be any of the $n-1$ edges in such an MST. So we could determine superheavy, other edges and also potentially super light edges that are in the MST built during the pre-Kruskal step using the algorithm outlined in John L's answer. So we can first mark the superheavy nodes only.

Now we modify the Kruskal step. We mark the edges which are added to the tree as superlight even though this is potentially only, they may not be. When an edge $(u, v)$ is added which would merge the forest as $u$ and $v$ are in the same component but it was not superheavy, we know it induces a cycle with edges added in previous weights and some of the edges marked as superlight. So we do a BFS rooted at $u$, one of the ends of the cycle in the currently built MST which is $O(n)$ since there are at most $n-1$ edges. This finds the unique and of course shortest path to $v$. At the same time we keep another disjoint set forest for the superlight edges. Then we go through parents of $v$ unmarking $(v, p[v])$ as superlight (only if its in the list of newly added superlight edges, or alternatively has the same weight of the current edge set) and merging $(v, p[v])$ in the disjoint set forest for superlight nodes. After all edges are processed for this weight, we add all the superlight edges to the disjoint set forest in $O(n)$ time if they were not added during cycle detection. So we do at most $n-1$ BFS's and unmark at most $n-1$ nodes because the forest allows only this many merges.

Now we have achieved $O(n^2)$ time which is better than I can find any references for in any literature or questions or answers. Almost every algorithm or suggestion so far has involved $O(mn)$ or $O(m^2)$ or $O(m^2+mn)$. I am not sure the superlight edges can be deduced in better time, but its with certainty that $O(n^2 \log n)$ time should be a sufficient bound to classify all the edges as superheavy, superlight or otherwise. We also get a specific MST as output in addition to all of the classifications.

The worst case will occur on a complete graph with all equal weights. And such a case indeed benefits from using this algorithm. Of course all the edges are other edges, but we know that as the cycles are induced we will find many edges inducing cycles ($n(n-1)/2-n-1$ of them in fact), but only $n-1$ of them will cause processing. $n(n-1)/2$ is incidentally the number of paths in a tree or the MST connecting all the nodes. Which is a pretty decent hint that the cycle determination can be done from the perspective of the potentially superlight edges.