0:36

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

Â 1:54

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.

Â 3:07

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.

Â 4:11

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.

Â 5:33

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

Â 6:42

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

Â 8:44

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

Â 10:14

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.

Â