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);
Complete the algorithm by specifying the property of vertex $u$ in each case.
What is the time complexity of the algorithm?
@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
Some points:
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.
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);
@rsansiya111
@gatecse Thank you sir. Nice explanation
@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.
64.3k questions
77.9k answers
243k comments
79.7k users