Let be a weighted undirected graph and let be a Minimum Spanning Tree (MST) of maintained using adjacency lists. Suppose a new weighted edge is added to . The worst case time complexity of determining if is still an MST of the resultant graph is
ANSWER
The worst-case time complexity is Θ(|V|), option (D).
Official answer: DSource: Official answer key, GATE 2020 CS (IIT Delhi)
T is a spanning tree of G, so it has exactly |V|-1 edges (independent of |E|), stored using adjacency lists.
When edge (u,v) is added, T (with one edge possibly swapped) remains an MST of the new graph if and only if w(u,v) is not less than the weight of the maximum-weight edge on the unique path between u and v in T — this follows from the MST cycle/cut property (if w(u,v) were smaller, swapping it in for that max edge would give a strictly lighter spanning tree).
To apply this test, find the unique u-v path in T (unique because T is a tree) and its maximum edge weight, e.g. by a BFS/DFS confined to T starting from u and stopping at v.
T has |V| vertices and |V|-1 edges, so this traversal over the adjacency-list representation costs Θ(|V| + (|V|-1)) = Θ(|V|).
None of the remaining |E| - (|V|-1) edges of G need to be examined, so the running time does not depend on |E|.
Hence the worst-case time complexity is Θ(|V|), which is option (D).
KEY IDEA
By the MST cycle property, adding an edge keeps an MST iff the new edge's weight is not less than the weight of the maximum-weight edge on the unique tree path between and ; since has only edges, finding that path and its max edge by a traversal restricted to costs , independent of .
WATCH OUT FOR
Assuming the check must scan the whole graph (all edges) or rerun a full MST algorithm such as Kruskal's (), instead of noticing that only the tree — with exactly edges — needs to be traversed.
From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes
