This slideshow introduces and explains the "Vertex Cover" Problem.
We start with some definitions and background.
A Vertex Cover of a graph is a set of vertices such that any edge of the graph is incident on at least one vertex of the set.
The smallest possible Vertex Cover of a graph is called the "Minimum Vertex cover".
1
2
3
4
5
6
7
The colored vertices in this graph form a Vertex Cover.
The Vertex Cover is {1, 3, 5}.
The following graph contains a Vertex Cover of size 6 (i.e. {1,2,3,6,9,10}).
1
2
3
4
5
6
7
8
9
10
The following graph contains a Vertex Cover of size 3 (i.e. {1,2,3}).
1
2
3
4
5
6
7
The Vertex Cover Problem can be defined as either of the following:
Given a graph G=(V,E), find the Minimum Vertex Cover in G. (Optimization form)
Or
Given a graph G=(V,E), and a number k, does G contain an Vertex Cover of size <=k? (Decision form)
Does the graph below have a vertex cover of size ≤3?
1
2
3
4
5
6
7
8
9
10
No
Does the graph below have a vertex cover of size ≤4?
Yes
