edited by
5,681 views
30 votes
30 votes

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);	
  1. Complete the algorithm by specifying the property of vertex $u$ in each case.

  2. What is the time complexity of the algorithm?

edited by

2 Answers

Best answer
9 votes
9 votes

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. 

  1. At each iteration we must select the vertex $u$ with the least degree
  2. $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);
selected by
28 votes
28 votes
  1. While adding vertex $u$ to $I$ it should not have an edge with any node in $I$.
  2. 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.
edited by

Related questions

19 votes
19 votes
3 answers
2
Kathleen asked Oct 5, 2014
2,694 views
What function of $x$, $n$ is computed by this program?Function what(x, n:integer): integer: Var value : integer begin value := 1 if n 0 then begin if n mod 2 =1 then val...