GATE CSE 1994 | Question: 24

Question

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:

V: Set of all vertices in the tree;	
I := ϕ
while	V ≠ ϕ do	
begin	
    select a vertex u ∊ V such that	
    _______;
    V := V - {u};	
    if u is such that	
    ________then I := I ∪ {u}	
end;	
Output(I);	

• A. Complete the algorithm by specifying the property of vertex $u$ in each case.

• B. What is the time complexity of the algorithm?

Comments

@Abhrajyoti00 where? 

---

@gatecse Sir, I meant that a maximum independent set is also maximal.

---

oh okay. Is this answer fine?
https://gateoverflow.in/2520/gate-cse-1994-question-24?show=391364#a391364

Answer 1

Some points:

1. An independent set of vertices of a graph is a set of vertices which do not have any edge in common
2. A maximal independent set of a graph is an independent set to which no more vertex can be added. A graph can have multiple maximal independent sets
3. A maximum independent set of a graph is the maximal independent set with maximum cardinality. A graph can have multiple maximum independent sets only when multiple maximal sets in it have the same maximum cardinality.

Reference: https://mathworld.wolfram.com/MaximumIndependentVertexSet.html

In the question we are asked to find the maximum independent set of a tree (a tree is a connected graph with no cycles). Finding the maximum independent set of a graph is an NP hard problem. But if the graph is restricted to a tree this problem not only becomes polynomial time solvable but can even be solved in linear time as shown here. The given algorithm in this question is using a greedy approach (not the optimal one). The greedy decision made here is to choose the vertex of minimum degree at any point. This greedy algorithm is guaranteed to work for trees and some other restricted class of graphs. 

• A. At each iteration we must select the vertex $u$ with the least degree
• B. $u$ is added to $I$ if there is no common edge between $u$ and any vertex in $I.$ For a single vertex this can take $O(|V|)$ time and hence for all the vertices this will take $O(|V|)^2$ time.

Complete algorithm is as follows:

V: Set of all vertices in the tree;	
I := ϕ
while	V ≠ ϕ do	
begin	
    select a vertex u ∊ V such that	
    degree(u) is minimum of all vertices in V
    V := V - {u};	
    if u is such that	
      no edge is common for u and any v ∊ I, then I := I ∪ {u}	
end;	
Output(I);

Comments

@rsansiya111

---

Very well explained. To find vertex with least degree every time, we can use a min heap.

---

@gatecse  Thank you sir. Nice explanation  

---

Really Amazing explanation in one answer revised many concepts.. Thank you sir.

Answer 2

• A. While adding vertex $u$ to $I$ it should not have an edge with any node in $I$.
• B. The algorithm runs till $V$ is empty (in $O(n)$ time) and is checking $u$ with each vertex $v$ in set $I$ (in $O(n)$ time). So, overall complexity $O(n^2)$ where $n$ is the number of nodes in the tree.

Comments

yes, there won’t be any time complexity improvement with sorted array – just that it is simpler to implement. We don’t need to actually delete any element as in iteration $i$ we just take array[i].

---

@Abhrajyoti00 we take sorted array of descending order.

---

@Argharupa Adhikary If we need min vertices every time, we could either sort in ascending order (extract a[0] every time) or in descending order (extract a[n-1] every time). Both are simple to implement and have same T.C of O(n) because we need to shift all the rest elements to make sure that the next time a[0] or a[n-1] produce the desired result. Thus there’s no extra advantage of using a descending array.

But we don't need to extract or shift also. We can just pick a[i] at $i^{th}$ iteration with no improvement in T.C.