Determine if an edge appears in all Minimum Spanning Trees

Question

Given a connected, undirected graph $G$, with arbitrary positive weights, and an edge $e$, how can I decide if $e$ appears in all possible minimum spanning trees? Is it possible to do in linear time - $O(|E|)$?

Answer 1

Let $H$ be the graph $G-e$, your graph with edge $e$ removed. If $H$ is disconnected, then yeah, $e$ has to occur in every minimum spanning tree. Otherwise if $H$ is connected, find a minimum spanning tree of $H$. Since the vertices that $e$ connects in $G$ are vertices of $H$ too, this minimum spanning tree of $H$ will also be a spanning tree of $G$. But then the question if this will be a minimum spanning tree of $G$? If it is, then the answer to your question is no, because you've found a minimum spanning tree that doesn't contain $e$. Otherwise if that spanning tree if not minimal for $G$, so there is a better spanning tree for $G$ that includes $e$, then yes, every minimal spanning tree must utilize $e$ because otherwise you would have found that tree in $H$.

Answer 2

Testing if the graph is connected takes $O(V + E)$ time. And in the worst case, you still have to find two MSTs, which takes $O(E \text{log}(E))$ time. I would do the following:

• Find an MST $T$ of $G$. If it does not contain $e$, then you are done.
• Otherwise, set $\text{wt}(e) = \infty$ and find an MST $T^{\prime}$ of $G$ with this modification. If $T^{\prime}$ contains $e$ or $\text{wt}(T^{\prime}) > \text{wt}(T)$, then $e$ necessarily appears in every MST of $G$.

Which has time complexity $O(E \text{log}(E))$. A linear time algorithm is doubtful to exist, as finding one spanning tree takes $O(E \text{log}(E))$ time, and there are at most $V^{V-2}$ spanning trees in a graph.

In certain special cases, we can avoid using the above algorithm based on the following observations:

• If $e$ is the smallest weight edge (and no other edge has the same weight as $e$), then $e$ appears in every MST. (Even more specifically, if the edge weights of $G$ are unique, $G$ has a unique MST).
• If $e$ is the heaviest weight edge on some cycle, then $e$ appears in no MST.