The next complicated problem that we're going to solve is called independent set. And the corresponding special case for which we are going to design a linear time algorithm is when an input graph is actually a tree. A real life application of this problem is the following, assume that you are organizing a company party. And you would like to invite to this party as many people as possible with a single constraint. You know that no person is going to enjoy your party if he or she is invited together with his or her direct boss. The mathematical model of this problem is the following. You are given a tree, and you would like to find in this tree a subset of vertices of maximum possible size, such that no two of them are adjacent. Okay, such that there is no edge between any two of them. So to give an example, consider the following tree. In this tree, there is an independent set of sides five shown here on the slide. There is also another independent set of size six. And an independent set of maximum size is shown here, and it has size seven. So our goal is to find efficiently, an independent set of maximum possible size, in any tree. As we've discussed before, this problem can be solved with a simple algorithm. The corresponding safe move in this case is the following. Take into a solution all the leaves. To prove that this algorithm is correct, we need to show that this step is safe, mainly that they always exist an optimal solution consistent with this step. In other words, that there exists a solution which contains all the leaves. To prove this, we usually argue as follows. We can take any solution, and we will transform it without decreasing its size so as to get a solution which contains all the leaves. In particular, if we start with an optimal solution, I mean, with the solution of maximum size. We will transform it into a solution whose size is at least the size of the initial solution, which means that this new solution is optimal, and it is also a valid solution. This will prove that the statement is correct. Well to explain how to transform it we, as usual, consider a toy example. So consider such a solution. So the blue vertices here are selected into an independent head. So we see that there are three leaves that are not included into our solution. So let's just take them into our solution. This will force us, also, to exclude all their parents but the crucial observation is that this does not decrease the size of the current solution. And the current solution is still a valid solution because for each of these leaves we excluded their parents. So this way, we get a solution of the same size, that includes all the leaves. And this proves that taking all the leaves in the solution is a safe move. The corresponding algorithm is quite simple. So, given that tree, you repeat the following while the three is not empty. Take all the leaves in the solution, then you remove from the tree all the leaves together with all its parents, and then you return the constructed solution. The running time for the current algorithm is if it is carefully implemented. In particular, you might want to do the following. For each vertex, you keep track of the number of its children. You actually do not remove anything from the tree itself. But you keep track of the current number of children for each vertex. So when you remove a vertex, you decrease by one the number of children of each parent. And you also maintain a queue that contains the vertexes of the do not have any children currently. So each iteration you know all the leaves of the current. This is are the exactly the vertexes with no children. Now let's generalize the problem. Assumed that you are still organizing a company party, but now instead of maximizing the number of people at the party, you are going to maximize the total fun factor of your party. Namely, each person is assigned some non-negative fun factor, and you would like to maximize the total fun factor of all the invited people. The mathematical model now is the following, you are given tree with weights on vertices, and you would like to find an independent set in this tree whose total weight is as large as possible, okay? To give an example, again, consider the following tree. One independent set in this tree is shown here in the slide. Its total weight is 17. And an optimal one has total weight of 18. As you see, it doesn't include all the leaves. So this problem cannot be solved by the same algorithm. We need to design a new algorithm for this problem. The new problem can be solved with a dynamic programming technique. When we have a problem on trees, it is very natural to try to define sub-problems for subtrees of this tree, and this is what we are going to do. For vertex v, denote by D(v), the maximum weight of an independent set in a tree rooted at the vertex v. Then there are basically two cases. Either we include v into, into our solution, or we do not include it. If we include it contributes the weight of this vertex to the total factor. And we also cannot take any of its children in the solution because otherwise it will not be an independent set. However, we can take anything from the subtree's root at its grandchildren. And particular, we are maximizing the total fun factor, so we would like to solve the problem optimally for all these subtrees. So, if we included what we can get, the maximum total fun factor that we can get is the weight of the vertex v plus the sum of all the optimal solutions for overall grandchildren w of v. On the other hand, if we do not include v in the solution, then we can solve the same problem independently for all its children. So the second case corresponds to the situation when we do not include v into our solution. And in this case, so this is our vertex v and this is, we do not include that into your solution. Then we can just solve it optimally for all its subtrees. And we can then take the sum of all these vertices. So since they state in the independent subtrees, the result in union of all the vertices. Is that we get from our subproblems is also an independent set into wall tree. We're going to use dynamic programming to implement the corresponding algorithms. Which uses direct relation that we've just discovered. Namely, the Function FunParty, for the vertex v, is going to compute the optimal answer for the subtree rooted at v, when we only go in to compute it if we haven't computed the corresponding value before. This is checked in the first if D(v) is still equal to infinity. So, at this point we assume that the niche earlier, D(v), is equal to infinity to all vertices. So, if we haven't computed this value before we start computing it. Then we check whether the vertex v is a leaf. If it is a leaf, then the answer is obvious. Then the obvious routine is to take this vertex into a solution. So the optimal answer is just the weight of this vertex. Otherwise, we need to compute its value recursively. We do this through grandchildren and children of the current vertex. The first case is when we take the vertex v into a solution. So first we initialize the variable m1 with the weight of the current, of the current vertex. And then derive through all grandchildren of the vertex v, this is done in these two loops. And we add to m1 the optimal answer for each grandchildren. We then proceed to the second case when we do not include v into solution. So m0 is initialized to 0, and then for all children u of vertex V. We need to add the optimal value for the corresponding children. This is down here. Okay, then we just select the maximum of the result into values and assign this value to D(v). And finally, we return D(v). The running time of this algorithm is also the goal of society of the tree and this is why. For each vertex there is just one serious call to FunParty. By serious, I mean a call which actually is inside this. Which gives rise to some computation, because after the first time when we are inside this loop for the vertex v, we will store the value in D(v) and then for any further call for FunParty(v) we just return the value immediately. Okay we just return it here. Note also that the value of D(v) is important for us only when we compute, only when we solve for sub problem can respond in to its parent and to its grandparent. Meaning that we will have only a constant number of calls to FunParty of v for each vertex v. We now show the result of applying this algorithm to our previous example. So in this tree we start to fill it in from the leaves to the root. So for each leaf, the value is computed in an obvious way. For example, for this subtree the answer is 1. For this subtree the answer is 2. And for this subtree the answer is also 1. For this subtree we need to make a decision. Either we take this vertex in which we gain 7, or we don't take it, in which case we can get 1 from here, 2 from here and 1 from here, which gives us 4. 7 is better. So an optimal independent set in this case, has total weight 7. For this vertex, its optimal value is 2 because it is a lift, and for this vertex, again, we need to select whether to take this vertex into a solution or not. If we can take it, then we cannot take the vertexes 7 and 2 it's children. So the value of the solution will be 6 plus the values of its grandchildren which are these. So the values of its grand children are 1, 2 and 1. So 6 + 1 + 2 + 1 = 10. So this corresponds to the case when we takes the root of the current subtree into solution. On the other hand, if we don't take it into solutions than the maximum that we can achieve is 7 in this subtree, and 2 in this subtree, which gives us 9. 10 is better than 9, so 10 is the optimal answer for this subtree. In a similar fashion, we get 5 here and we get 3 here. Now for this vertex, again we need to select whether is better to include it into the solution or it is better to have waited. If we included the itinerary solutions and the maximums that we can we get a 3 plus, in this case if we included into solution we can not use it's children, but we can use anything in the subtree rooted by it's grandchildren. So we can get 2+3+7+2. So this gives us 3+2+3+7+2, which is equal to 17. Right, if on the other hand we do not include it, then we can get anything we want from the subtrees through it's children. This will give us 5+3+10. 5+3+10=18 which is better so we conclude that 18 Is the best we can do for this toy example. So this concludes the lecture for the special cases of complete problems. Let me remind you the main idea once again. The fact that your problem is incomplete does not exclude the possibilities that. Some special cases that arise in practice of this problem can be efficiently solved, and we've just seen two such examples. Despite of the fact that the satisfiability problem is difficult, in the general case its special case is, namely, if all the clauses of a formula contain at most two literals can be easily solved in minimal time. The second example was about independent set. This problem is hard in general, so given a graph, it is difficult to implement an algorithm which always finds an optimum size independent set of a graph. But, if you know that all of your graphs that are right in your application are trees, then it is easier to implement a linear time algorithm that will find an optimal answer quickly.
