The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+20 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	
    select a vertex u ∊ V such that	
    V := V - {u};	
    if u is such that	
    ________then I := I ∪ {u}	
  1. Complete the algorithm by specifying the property of vertex $u$ in each case.

  2. What is the time complexity of the algorithm?

asked in Algorithms by Veteran (52k points)
edited by | 1.1k views

Just additional information ->

maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of G, and denoted α(G).[2] The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem.

Reference -->

1 Answer

+18 votes
Best answer
  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)$.
answered by Boss (33.8k points)
selected by
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(n2).


here adjacency matrix is used. otherwise with adjacency list complexity will be O(n3) . 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?

i think yes
@arjun sir

why would we include check cost in time complexity?
    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}	

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

@arjun sir plz confirm this


how ?


You are right. 


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.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,582 questions
54,192 answers
71,147 users