Our last hard set problem that we mentioned here, deals with graphs again. It is called an independent set problem. Here, we're given a graph and the budget b. And our goal is to select at least b vertices such that there is no edge between any pair of selected vertices. For example, in this graph that we've seen before in this lecture, is there is an independent set of size seven? So the selected vertices are shown here in red. And it is not difficult to check that there is no edge between a pair of red vertices. And the particularization implies that an independent set is indeed a search problem. It is easy to check whether a given set of vertices is an independent set, and that it has size at least b. It is interesting to note, that the problem can be easily solved if the given graph is a three. Namely, it can be solved by the following simple greedy strategy, given a tree if you want to find even just the independence side of maximum size we can do the following. The first thing to do is let's just take all the leaves into a solution. Then, lets remove all the leaves from the three together with all its parents. And then, lets just continue this process. To prove that this algorithm produces and optimal solution, we need to show the take in all the leaves and our solution is a safe move, that it is consistent with an optimal solution. This is usually done as follows. Assume that there is some optimal solution in which not all the leafs are taken. Assume that, just for concreteness, assume that this is suboptimal solution. Not all the leaves are taken here because, well, we have this leaf, this leaf, and this leaf, which is not in the solution. Then we show that it can be transformed into another solution which, without decreasing its size, such that it contains all the leaves. Indeed, let's just take all these market leaves into a solution. This will probably require us to discard from a solution all it's parents, but it will not decrease the size of the solution. So what we get is another solution whose size is, in this case, actually the same. But it contains all the leaves. Which proves that there always exists an optimal solution which contains all the leaves. And this in turn means that it is safe to take all the leaves. We will see the details of this algorithm later in this class. But in general, once again, if we are given a tree then we can find an independent set of maximum size in this tree. Very efficiently in linear time. But at the moment, we have no polynomial algorithm that finds, that even checks where there's a reason and independent set of size b in the given graph in polynomial time.