The first problem for which we are going to design an approximation
algorithm is called the vertex cover problem.
The input of this problem consists of a non-directed graph.
And what we'd like to find is a subset of its vertices of minimum size,
which touch or covers every edge.
To give a specific example, consider the following graph of eight vertices.
Well for any graph, we can take all the vertices into a cover.
This is clearly a vertex cover, it touches every edge.
And the other thing is, in this graph, we can also take the following six vertices.
It is not difficult to see that each edge is touched by green vertices.
And an optimal vertex cover in this case consists of the following three vertices.
Again, it is not difficult to check that for each edge,
at least one of its endpoints is green.
For example, for this edge, it is covered with this vertex.
For this edge, it's covered with two green vertices, and
there are no vertices that was not green, they are connected by a niche.
So the green set of vertices indeed touch every edge.
The approximation algorithm for
this problem that we are going to consider is surprisingly simple.
Namely it works as follows.
Initially our Vertex Cover is empty, so, we initialize C as an empty cell.
Then we repeat the following while the set of edges of our graph is not empty.
We select any edge denoted by u,v of the current set of edges and
then we add these vertices to the set C.
Then we remove from the graph all edges that are already attached by U and V.
So we remove all edges that are adjacent to U or V.
So we repeat this while there is at least one edge in E,
and when E is empty we just return C.
Let me illustrate this on our previous graph.
So first assume that we select this red edge.
Then we add its two vertices to a solution, and
then we remove from the graph all edges adjacent to these green vertices
because they are already covered.
We did not need to cover them.
Then we select some other edge, for example this one,
we add to its endpoints in the solution, and we remove all edges
that are adjacent to these two newly added green vertices.
So this leaves just one edge in our graph, so we select it, and
we add two vertices into our solution.
And we get the following,, the following solution consisting of six vertices.
So just to show that it is indeed a solution,
let me show you the initial edges of the graph.
So we see the green vertices,
the six green vertices indeed cover all the edges of our initial graph.
We are now going to prove that the present algorithm is 2-approximate.
This means that the running time of this algorithm is pretty normal and
also that the solution, which is found by this algorithm,
is at most twice as large as the optimal solution.
Well the fact that the running time of our algorithm is polynomial is clear
just from its implementation.
In fact, its running time is linear.
So we proceed to show that it returns a solution, which is at least at most,
twice as large as an optimum one.
First observe that the set of edges selected by our algorithm
is it forms a matching.
This means that all the end points of edges selected by our algorithm,