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?

edited | 943 views
+4

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.

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)$.
selected
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

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
0

1
2