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

Complexity should include the property check cost rt?

---

That is checking u with each vertex v in set I. In worst case this be O(n). So, overall complexity O(n²).

---

here adjacency matrix is used. otherwise with adjacency list complexity will be O(n³) . right?

---

 select a vertex u ∊ V such that	
    _______;
    V := V - {u};	
    if u is such that	
    ________then I := I ∪ {u}

At the second blank space we have to check whether it is directly connected to any vertex of set I...right ??

And what should be at first blank  ??

---

Is it an application of graph coloring?

---

The first part has two blanks, will both of them get the same fill?

---

@bhuv

i think yes

---

@arjun sir

why would we include check cost in time complexity?

---

begin	
    select a vertex u ∊ V such that	
    u with minimum degree; //greedy approach
    V := V - {u};	
    if u is such that	
    u is not adjacent to any of I
   then I := I ∪ {u}	
end;

Time complexity : $n*O (n)=O(n^{2})$

@arjun sir plz confirm this

---

@tanu

how ?

---

 reena_kandari

You are right. 

---

@rahul

i dont understand how to arrive at this complexity

can you explain ?

---

refrence to the solution by reena_kandari

while loop will run for all the set of vertices in the graph .... say n

inside while loop the vertex u will  checking whether adjacent or not with every is .... hence O(n)

total n*O(n)= n^2

---

Greedy approach for such maximum independent set problem does not always succeed.

Ref:

https://semidoc.github.io/greedyMIS

---

http://www.cs.toronto.edu/~fpitt/20129/CSC373/lectures/TS12.txt

---

So the complexity will be O(|V|^2), right?

---

Nope....graph coloring is similar to independent set...when you colour the graph since no two adjacent vertices should not be coloured with same colour so they form independent set.

---

https://www.di.ens.fr/~mmari/content/papers/rapport.pdf

 

The explanation is in the link for greedy approach.

---

Since this is a greedy algorithm, the first blank should be, find the vertex with minimum number of degree.

second blank- check if the vertex has an edge to any of the vertex included in independent set.?

If an array is maintained storing the number of degrees of all vertices, this algo will take O(V^2) ,

is this approach wrong?

---

Coming to Time complexity

First blank ->  select the vertex which has minimum degree..

We can clearly say that order of the degree may not be in proper order .

Selecting minimum takes O(n^2)

Worst case

Second blank;

If the vertex is not in the I list...add it  to the List I

Checking takes O(n^2) in worst case

So total

O(n^2)+O(n^2)

==O(n^2)

---

MiNiPanda In your given link, counter-example is given for MIS problem for graphs. In question MIS problem for trees is asked.
Page 6 of https://www.di.ens.fr/~mmari/content/papers/rapport.pdf says:

Some graphs where Greedy is optimal:
In particular any vertex of degree one belongs to a maximum independent set. For this reason Greedy will always produce an optimal solution on trees.

MIS problem for trees can be done by both greedy and dynamic approach in O(n) time complexity. See page 11 here: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/10ExtendingTractability.pdf

---

Good but bad

---

I think first we should build a min heap of n vertices according the degrees. take O(n).

then delete them n times(takes O(nlogn). and check whether one vertex is adjacent to the rest of the vertex in I set. In total this will take O(n^2).

So the overall time complexity is O(n) + O(nlogn) + O(n^2).

so O(n^2).

---

@Rajarshi Sarkar Kindly explain sir 

---

@rsansiya111 we can follow @gatecse ‘s ans and @Argharupa Adhikary has given a nice approach to find the min vertex. 

---

@Argharupa Adhikary do we need a decrease key operation here? If not cannot we use a sorted array instead of min heap? 

---

@gatecse

we don’t need a decrease key operation. Here in second dash, we only check the other vertices are adjacent to the min degree vertex or not.

we can definitely use sorted array in place of min heap but to  delete from sorted array in descending order,it will take O(1). but checking adjacencies in second dash will take O(n^2) in total. So no improvement will be there.

---

@Argharupa Adhikary Deleting from Sorted array will take O(n) as we again need to shift all the elements.

---

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.