GATE CSE 2020 | Question: 31

Question

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 weighed 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

• A. $\Theta (\mid E \mid + \mid V \mid) \\$
• B. $\Theta (\mid E \mid \mid V \mid) \\$
• C. $\Theta(E \mid \log \mid V \mid) \\$
• D. $\Theta( \mid V \mid)$

Comments

It’s Quite Easy.

Adjacenct List is there so, atmost it can takke O(|V| + |E|)

Option (B) and (C) is not be there.

Let us check can we do some better?

The MST will have |V|-1 edges having their weights.

Therefore the time complexity to traverse the Adj. List = O(|V|+|V|-1) = O(|V|)

we can do this:

for i=1 to |V|-1 do{

     for each edge (u,v) belongs to the MST{

                  if(weight(u,v) > w(new edge){

                                print(“No More MST”);

                                                                }

}

}

Time Complexity:

Outer For Loop Runs for |V| -1 times O(|V|)

second for loop runs for sum(degree(V)) times  = O(|E|) = O(|V|) times.

---

@ShouvikSVK

   if(weight(u,v) > w(new edge)

how does this guarantee’s that after adding the new edge it will not be the MST? may be after adding the new edge our previously added edge(having edge wt. less than the new edge) is forming some cycle?

---

i didnt understood solution anyone please comment down any youtube video link?

Answer 1

We can do this in $O(|V|)$ in the following way:

1. Run $\textsf{BFS}$ in $T$ from $u$ to $v$ to detect the edge with maximum value in that path. $-O(|V|).$
2. If the weight of that edge is greater than the weight of the edge you're trying to add, remove that old edge and add the new one.
3. Otherwise, do nothing, because the new edge would not improve the $\textsf{MST}.$ $-O(1).$

The rationale behind this solution is that simply adding an edge into $T$ would create exactly one cycle, and to restore the $\textsf{MST}$ property we have to remove the edge with maximum value from that cycle.

Source: https://stackoverflow.com/questions/30881340/update-minimum-spanning-tree-if-edge-is-added

Comments

Even if we don’t know the newly added edge weight we can find if the tree is same:

1. We traverse the new MST with the edge added. ( It has a cycle now ); so traversing will take O(V).
2. After traversing we will get the edge with the maximum weight.
3. We remove that edge and now we don’t have any cycle. Now just find if that MST is same as previous.
4. We can check if they are same or not by maintaining adjacency list and comparing both.           O(V)

---

@Arjun @Sachin Mittal 1 @Deepak Poonia Sir,

Run BFS in T from u to v to detect the edge with maximum value in that path.

So how can we implement using BFS?

→ We will run the BFS function on vertex u and count the maximum value in the path from u to v.

(y,x) → will indicate the edge weight between vertex y and x.

vertex.max → will store the maximum weight from u to that respective “vertex”.

Algorithm:

u.max=0;

BFS(G,u)

{

     visited[u] = true;

      add(u,Q)

      while(Queue is not Empty)

     {    x = delete(Q);

          for each adjacent y to x

          {

                 if( y = = v)

               {

                   if(x.max<(y,x))

                      y.max= (y,x)

                  else 

                     y.max = x.max

                 return;

                }

                 else if(visited[y] == false)

                 {

                            visited[x] = true;

                            add(x,Q);

                            if(x.max<(y,x))

                                 y.max= (y,x)

                           else 

                                y.max = x.max

                   }

              }

          }

   }

                            

---

what if that new added edge create cycle in MST, how that case will be covered here?

Answer 2

You can imagine that there must be a cycle between the nodes u and v. Now if the newly added edge has less weight that any of the previous edge joining u and v, then you just need to replace the maximum weighted edge in that cycle with the newly added edge. In case it is not less that any of them, then no changes needs to be done. In worst case MST can have |v|-1 edges. So O(|v|) would be the answer.

option D.

Ref:- https://www.arl.wustl.edu/~jst/cse/542/exams/ex1sol.pdf

Comments

No G = (V,G) is given in the question which means G is a graph which represents V vertices and G edges. They should have given G =(V,E) then we can say for sure what E means. If that was a printing mistake then they are supposed to give marks to all coz we can assume E as no of edges in T also as nowhere E is mentioned in the question except the options and I know it looks like I am fighting too much but sometimes we notice the small details and lose marks :(

---

No. That was a typo while editing. Fixed now.

---

Oh alright I actually just took 2020 gate test today from GateOverflow and the question in it also had the same typo. So i thought that was the actual question.

Answer 3

The key observation is that in a tree, between any two vertices there is a unique simple path. Therefore, once we add an edge between any two vertices in a tree, we will get exactly one cycle in the tree.

By cycle property of MST, we know that the maximum cost edge in a cycle in G cannot be part of our MST. Therefore, our job is to figure out the maximum cost edge in the cycle being formed. If it is the new edge, it is of no use and our MST remains same. If the maximum cost edge is not the new edge, we have to delete it and our MST will not remain the same.

Let T be the MST for the given graph G.

ALGORITHM :

1. Find the maximum edge weight in the path from vertex u to v in T. We can use DFS for this as shown in the pseudo-code below : 

   struct node {
       int vertex;
       int weight;
   };
   
   int maxEdge;
   
   void dfs(int u, int pathMax, vector<bool>& visited,vector<node>& adjList[]) {
       visited[u] = true;
       if(u == v) {
           maxEdge = pathMax;
           return;
       }
       for(node n : adjList[u]) {
           if(visited[n.vertex] == false) {
               if(n.weight > pathMax) {
                   dfs(n.vertex, n.weight, visited, adjList);
               } else {
                   dfs(n.vertex, pathMax, visited, adjList);
               }
           }
       }
   } 
   // initial value to pathMax is INT_MIN

2. Time Complexity for this step is O(|V| + |E|). But for a tree, |E| = |V| – 1. Therefore, the cost for this step is O(|V|).
3. Now, once we have the maximum edge weight between u and v, we can compare this with the new edge weight. If new edge weight is greater than the maximum edge weight between u and v , then our MST remains same. In the other case, we have to delete the edge with maximum edge weight between u and v, therefore our MST changes. Cost of this step is O(1).

Therefore, total time complexity for our algorithm is O(|V|).

 

Answer 4

First of all, for distinct weighted graph we can’t do bfs.

So what we can do for this,

Already we know for minimum weight spanning tree with V vertices,we have V-1 edges.Also to traverse adjacency list ,time complexity required is O(V+E) and here for V-1 edges we have O(V) time complexity.

So while traversing adjacency list of T, we can compare the newly added weight with the weights on the node .If the newly added weight is smaller then will be change in minimum weight spanning tree otherwise not.

So we can say time complexity is O(V)

Comments

@samarpita one small doubt

 Why TC isn't O(V+E) ??

"Also to traverse adjacency list ,time complexity required is O(V+E) "

Due to this? 

---

The catch here is in the question, The tree is given instead of the Entire graph

and in a tree $E = V-1$ , Hence TC = $\Theta(V+E) = \Theta(V+V-1) = \Theta(V)$

---

@Shubhodeep oh yes great observation 

thanks 👍👏