Determine if an edge appears in all Minimum Spanning Trees
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|)$?
$\endgroup$ 03 Answers
$\begingroup$Yes, there is a simple $\mathcal{O}(|E|)$ algorithm.
Here is the full statement.
Given a (simple finite non-multi) connected undirected weighted graph $G$ with edge set $E$ and an edge $e$, we can determine whether $e$ appears in all MSTs of $G$ in $\mathcal{O}(|E|)$ time.
Here is the description of the wanted algorithm.
- Remove $e$ from $G$.
- Let $u$ and $v$ be the two vertices of $e$. Run a standard DFS or BFS on $G$ starting from $u$ along edges that are either lighter than or as light as $e$ to see whether we can reach $v$.
- If we can reach $v$, then some MST does not contain $e$. Otherwise every MST contains $e$.
The time-complexity of the algorithm is $\mathcal{O}(|E|)$ since both step 1 and step 2 take $\mathcal{O}(|E|)$ time.
What the algorithm does is simply to determine whether there exists a cycle that contains $e$ and none of whose edges is heavier than $e$. In other words, the algorithm checks whether $e$ is one of the heaviest edges in any cycle.
The correctness of the algorithm comes from the following characterization of edges in all MSTs.
Theorem on characterization of an all-MST edge: An edge $e$ appears in all MSTs if and only if $e$ is not one of the heaviest edges in any cycle.
Here is the proof of the theorem.
the "if" part: Suppose $e$ is not one of the heaviest edges in any cycle. Let $u$ be a vertex of $e$. Let $H$ be all vertices that can be reached from $u$ by a path not containing $e$ whose edges are either lighter than or as light as $e$. We can verify that $e$ is the unique lightest cut crossing $(H, G\backslash H)$. So any MST must contain $e$.
the "only if" part: Suppose $e$ appears in all MSTs. Let $C$ be a cycle containing $e$. Let $m$ be an MST. $m$ without $e$ consists of two disjoint trees, which we call $m_1$ and $m_2$. Connecting $m_1$ and $m_2$ by $e$, cycle $C$ must also connect $m_1$ and $m_2$ at another edge $e'$. If we replace $e$ with $e'$ in $m$, we obtain a spanning tree that does not contain $e$, which we call $m'$. $m'$ is not an MST. Since the only different edges between $m$ and $m'$ are $e$ and $e'$, $e$ must be lighter than $e'$. That is, $e$ is not one of the heaviest edges in $C$.
$\endgroup$ 5 $\begingroup$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$.
$\endgroup$ $\begingroup$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.
