Some points:
- An independent set of vertices of a graph is a set of vertices which do not have any edge in common
- 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
- 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.
- At each iteration we must select the vertex $u$ with the least degree
- $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);