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.