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 $\leq 3$?
1
2
3
4
5
6
7
8
9
10
No
Does the graph below have a vertex cover of size $\leq 4$?
Yes
