This slideshow introduces and explains the "Independent Set" Problem.
We start with some definitions and background.
An Independent Set of a graph is a set of vertices such that no two of them are connected. That is, there exists no edge between any two vertices of an Independent Set.
The largest possible Independent Set of a graph is called the "Maximum Independent Set".
1
2
3
4
5
6
7
The colored vertices in this graph form an independent set.
The Independent set is {1,3,5,7}.
The following graph contains an Independent Set of size 3 (i.e. {2,4,5}).
1
2
3
4
5
The following graph contains an Independent Set of size 5 (i.e. {2,3,4,6,10}).
1
2
3
4
5
6
7
8
9
10
The Independent Set Problem can be defined as either of the following:
Given a graph G=(V,E), find the Maximum Independent Set in G.(Opimization form)
Or
Given a graph G=(V,E), and a number k, does G contain an Independent Set of size >= k? (Decision form)
Does the graph below have an independent set of size >=9?
1
2
3
4
5
6
7
8
9
10
11
No
Does the graph below have an independent set of size >=7 ?
