GATE CS 2020 Q31 — Minimum Spanning Trees

To determine if the tree $T$ remains a Minimum Spanning Tree (MST) after adding a new weighted edge $e = (u, v)$ with weight $w(e)$, we can use the Cycle Property of MSTs.

1. Theoretical Background

When a new edge $e = (u, v)$ is added to the tree $T$, it creates a unique cycle $C$ consisting of the edge $e$ and the unique path between $u$ and $v$ in $T$.

• According to the cycle property, $T$ remains an MST of the new graph if and only if the newly added edge $e$ has the maximum weight in this cycle $C$.
• In other words, $T$ is still an MST if and only if: $$w(e) \ge \max \{ w(e') \mid e' \text{ is an edge on the path between } u \text{ and } v \text{ in } T \}$$

2. Algorithm and Time Complexity

To verify this condition, we perform the following steps:

1. Find the unique path between vertices $u$ and $v$ in the tree $T$ using a standard graph traversal algorithm like Depth-First Search (DFS) or Breadth-First Search (BFS) starting from $u$.
2. During the traversal, keep track of the maximum edge weight encountered on the path to $v$. Let this maximum weight be $w_{\max}$.
3. Compare the weight of the new edge, $w(e)$, with $w_{\max}$. If $w(e) \ge w_{\max}$, then $T$ remains an MST; otherwise, it does not.

Since $T$ is a tree, it contains exactly $|V|$ vertices and $|V| - 1$ edges. Running DFS or BFS on a tree represented by adjacency lists takes time proportional to the number of vertices and edges in the tree:

Thus, the worst-case time complexity of determining if $T$ is still an MST is $\Theta(|V|)$.