Hello, and welcome to the next and actually the last lesson in the Coping with NP-completeness module. In this lesson we're going to design approximation algorithms. Such algorithms work in depending on the size of the input and plus their return. Is might not be an optimal solution but it is guaranteed to be a solution which is close to optimal. 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, the end points of all the edges are just joined. Why is that? Well, assume that this is the first edge selected by our algorithm. So this is u, v. Recall that after selecting this edge, the algorithm, discards all the edges adjacent to u and v, which means that for this algorithm, Neither this, neither this and point coincides with u of v, neither this one. This is also, this also means that any vertex cover must take at least one vertex from each of these edges, which in turn means that any vertex cover of our graph must If you have size, it leaves the current analogy, or the size of M, right? Now that the same times that we know the size of the vertex covered returned by our algorithm. It equals to just 2 times the size of M. This is just because the size of M is the number of edges in the set M and each edge has two vertices, two end points. So this allows us to conclude that the size of the vertex cover found by our algorithm is equal to 2M precisely. And we know that M is at most the optimum value, the size of the optimum vertex cover. So 2M is at most two times OPT which justifies that what our algorithm returns is a vertex cover whose size is at most twice the size of an optimum vertex cover. Let me also show you the set of edges selected by our algorithm in the previous example so it selected the following three edges. And you can see that indeed, all these three edges form a matching. So the end points of these three edges are disjoined. And this also means that to cover these three edges, we must take at least three different vertices. So we must take either this vertex or this vertex to cover this, to cover this edge. And this will not help us to cover any of the other red edges right? So we also must take either this vertex or this vertex and then either this vertex or this vertex. In total, at least three vertices. Let me emphasize here the following thing. So we have somehow managed to prove that the size of the vertex cover constructed by our algorithm is at most 2 times the optimal value. At the same time, note that we do not know the optimal value. We do not know how to compute it in polynomial time. So our algorithm runs in polynomial time. So we don't know how to compute optimal polynomial time. So our algorithm doesn't compute it. However, what it computes is that we know for sure that it is at most twice times the optimal value. So how it can possibly be that we proved some upper bond on C in terms of OPT without knowing the exact value of OPT? Well, this is because we know some lower bond are not and it is the size of the matching that we constructed. So the size of M gives a good lower bound on OPT. More over the matching M can be used to construct some vertex cover. And just by taking all the end points of these M edges we get a vertex cover whose size is twice the size of M so this gives us the final lower bound. So C is equal to two times M, which is, in turn, at most, two times OPT. So this allows us to prove an upper bound on C. Not in terms of some quantities that we don't know, namely OPT but in terms of the size of M which we can compute quickly and which we can use to construct the vertex cover. Let me conclude this video with a few remarks. So first of all the bound we've proved that our algorithm is to approximately tied. This means that there are graphs for which our algorithm will return, an answer which is exactly twice as large as an optimum vertex cover. And this can be viewed as follows, lets just consider a full, well a full bipartite graph. Or we can just, just consider the following bipartite graph, okay. Assume that we have n vertices here and n vertices here. So our algorithm is going to do the following. So with each step, it will select one vertex, one edge, and add the both vertices to the solution. So in the end it is going to return a solution of size 2n, right? At the same time all the edges of this graph can be covered just by one of its part. So there is a solution of size m, but our algorithm returns a solution of size 2m. The last remark is that surprisingly, this algorithm is almost the best one that we know. In particular, we do not know how to find an approximation of this algorithm with the factor 1.99, for example.