GATE CS 2020 Q.41 (CS Q.31): Greedy Algorithms

Let $G = (V, E)$ be a weighted undirected graph and let $T$ be a Minimum Spanning Tree (MST) of $G$ maintained using adjacency lists. Suppose a new weighted edge $(u, v) \in V \times V$ is added to $G$ . The worst case time complexity of determining if $T$ is still an MST of the resultant graph is

$O(|E| + |V|)$

$O(|E| |V|)$

$O(|E| \log |V|)$

$\Theta(|V|)$

Official answer and solution

Official answer: D
From: Official GATE 2020 answer key

Solution

Use the Cycle Property of Minimum Spanning Trees to analyze the complexity of checking the new edge.

MST Cycle Property:

Adding a new edge $e = (u, v)$ with weight $w(e)$ to an existing MST $T$ creates exactly one simple cycle $C$ , formed by edge $e$ together with the unique tree path between $u$ and $v$ in $T$ .
$T$ remains an MST of $G \cup \{e\}$ if and only if $w(e)$ is greater than or equal to the weight of every edge on the tree path between $u$ and $v$ in $T$ (i.e., $e$ is a maximum-weight edge on cycle $C$ ).

Time complexity to test this condition:

$T$ contains $|V|$ vertices and $|V| - 1$ edges.
Traversing $T$ from $u$ to $v$ via Breadth-First Search (BFS) or Depth-First Search (DFS) visits at most $|V|$ vertices and $|V| - 1$ edges, taking $\Theta(|V|)$ time.
During the traversal, tracking the maximum edge weight along the path takes $O(1)$ per edge visited.
Comparing this maximum with $w(e)$ takes $O(1)$ time.
Hence, the worst case time complexity is $\Theta(|V|)$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 41 of 65, printed as CS Q.31
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source