How a fast reduction is from the Independent Set problem to the Vertex Cover have a problem? We call that, in the independent set problem, we're given a simple and direct graph and weight it together with the budget b. And our goal is to find at least b vertices in this graph such that, there are no edges between any pair of them. The vertex cover is formulated as follows, the vertex cover problem. We are again given a graph, a simple, unweighted, undirected graph, together with the budget b. And our goal is to find at most b vertices that cover all edges of our graph. That is, any edge of this graph has at least one end point in the selected set of at most b vertices. Let's consider for example, in this graph, we have eight vertices, and one example of an Independent set of this graph is E and C. It is interesting to know that in this case, we cannot add any other vertex to this Independent set. For example, if we add the vertex B, then we will violate the properties that there is no edge between two vertices because there is an edge between B and C. We cannot add F because it is connected to E. We cannot add A because it is connected to E. Cannot add H, cannot [INAUDIBLE] D because it is connected to C and so on. So we cannot extend the independent set. You see in this case, still there is a larger independent set in this case. It includes vertices A, C, F, and H. It has size four. It is not difficult to check that it is indeed an independent set, that no two red vertices are joined by an edge in this graph. Concerning vertex cover, one vertex covering this in this graph had size six. It includes all vertices except for E and C. It is indeed not difficult to check that for any edge in this graph, at least one of its endpoints is green. For example, for this edge that this endpoint, there's the vertex G has selected for this edge, both of its endpoints are included into the vertex cover. Recall that we're interested in vertex covers of small size, and in this case, there is a smaller vertex cover, it is a set B,E,G, and D. And again, it is not difficult to check that these being vertices touch all the edges of our graph. By reviewing this example, you probably already noticed the following simple property of independent sets of a graph and its vertex covers. I is an independent set of the graph G even though V it's complimentary set of vertices is a vertex cover in this graph. Let's prove this formula. So I assume that I is an independent set, this essentially means that there are no edges in both end points in the set I. This in turn means each edges at least one end point in the complimentary settings of E minus I. And this in turn means three minus I is a vertex cover of a graph, right? For the reverse direction, I assume that V minus I is a vertex cover of the graph. This means that V minus I touches every edge. This again means that for each edge, at least one of its endpoints lies in V minus I. And this means that for no edge, two of its endpoints lie in I, which in turn gives us that I is an independent set of the graph G. This relation allows us to design a very simple reduction from the independent set problem to the vertex cover problem. Namely, to check whether the given graph G contains an independent set of size at least b. We just check whether the same graph G contains the vertex cover of size at most V minus b. We already know that there is an independent set of size at least b, if and only if there is a vertex cover of size at most b. So formally, our reduction is specified by two very simple and clearly polynomial time algorithms. Algorithm F needs to transform an instance of the problem independent set to the instance of a vertex cover problem. So we take an G and the budget b, and we'll leave the graph G untouched, and we'll replace the budget by V minus b. Then we call an algorithm as a black box, an algorithm for the vertex cover problem on the following instance. If it finds out that there is no vertex cover of size at most V minus b in this graph, then we just report immediately that there is no Independent set of size at least b in our initial graph. Otherwise, it returns as some solution S which is a vertex cover in the graph G of size at most V minus b. By taking the complimentary of this set S, we get a vertex cover of size at most b.