The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
943 views

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?

asked in Algorithms by Veteran (59.6k points)
edited by | 943 views
+4

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 --> https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

1 Answer

+15 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 (34.1k points)
selected by
0
Complexity should include the property check cost rt?
+1

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

0

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

0
 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  ??

0
Is it an application of graph coloring?
0
The first part has two blanks, will both of them get the same fill?
+1
@bhuv

i think yes
0
@arjun sir

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

0
@tanu

how ?
+1

 reena_kandari

You are right. 

0
@rahul

i dont understand how to arrive at this complexity

can you explain ?
0

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

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

Ref:

https://semidoc.github.io/greedyMIS

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

42,603 questions
48,602 answers
155,709 comments
63,753 users