Finding a minimum spanning tree that shares the minimum number of edges with the given one

Question

Given some undirected weighted graph $\ G(V,E, w) $ and its minimum spanning tree $\ T$, I need to find another spanning tree $\ T' $ with minimal amount of common edges of both trees. If there are no other spanning trees then $\ T' = T $

I was thinking maybe if I can "subtract" the edges of the minimum spanning tree I was given from the original graph edges and then this subset of edges that I've left with is my starting point for running prim algorithm and if I can not find other MST then any $\ T' = T $ does that make any sense at all ?

Answer 1

Instead of "subtract", it is easier to "try to avoid".

---

Sort all edges first by their weights, then by whether they belong to $T$. In other words, for any two edge $e_1$ and $e_2$, $e_1$ precedes $e_2$ if and only if

• $w(e_1) \lt w(e_2)$, or
• $w(e_1) = w(e_2)$ and $e_1$ does not belong to $T$ and $e_2$ belongs to $T$

The above order can also be realized by just increasing all weights of edges in $T$ by a small enough amount, such as $\frac d2$, where $d$ is the minimum positive difference between weights of any two edges.

Run Kruskal's algorithm or Prim's algorithm as usual using the above order of the edges instead of the usual order which sorts the edges by weights only. Since the edges are ordered by their (original) weights still, we will obtain a minimum spanning tree, which is $T'$.

---

On the other hand, you idea to "subtract" works as well.

Let $S$ be the all edges of $T$. For each edge $e\in S$ from the lightest to the heaviest,

1. remove $e$ from $T$. $T$ becomes two disjoint trees
2. check whether there is an edge other than $e$ of the same weight that connects those two disjoint trees.
   • If we are able to find one, add it to $T$.
   • Otherwise there is no such edge. Add $e$ back to $T$.
3. return $T$, which may or may not have been changed, as $T'$.

However, the algorithm above is harder to implement and probably slower as well.