There is no grid here. The table has one entry per vertex, and the entry is a pair: the best total in that vertex's subtree with the vertex taken, and the best without it. One postorder pass fills both, because a vertex's children are finished before it is. The set that comes back is then checked to be independent — against the edge list, not against the structure the pass walked — and re-weighed.
Core ideas
The hard idea is that the fill order is the tree's own postorder, so it is forced by the structure rather than chosen — and the structure is what the argument depends on.
For each vertex, the best total obtainable within its subtree if that vertex is in the chosen set, and the best if it is not. Taking a vertex forbids all its children, so with(v) sums the children's without. Declining it frees each child to do whichever is better for itself, so without(v) sums the children's maxima. Two numbers, one recurrence each.
Every read is from a child, and postorder finishes every child before its parent, so no read lands on an unfilled entry. There is no ordering decision to get wrong here — which is worth noticing precisely because the matrix chain had one and got it wrong. The tree's shape is the order.
The argument uses that a child's subtree interacts with the rest of the graph only through its parent. In a graph with a cycle that is false, the subtrees overlap, and the same pass would still produce a number. So the lab refuses an edge list that is not a tree — a cycle, a self-loop, a forest — rather than answering about a graph its recurrence does not describe.
The material
The problem, the pair recurrence and its proof, why the order is free here, and the two checks on what comes back.
A set of vertices is independent if no edge joins two of them. Given a weight on each vertex, the maximum weight independent set problem asks for an independent set of largest total weight. On a general graph this is NP-hard; on a tree it is one pass, and this lesson is about why the difference is the tree and not the cleverness.
Root the tree anywhere. For a vertex v with children u, let with(v) be the largest total over independent sets in v's subtree containing v, and without(v) the largest over those not containing it. Then with(v) = weight(v) + sum of without(u) and without(v) = sum of max(with(u), without(u)), and the answer is max(with(root), without(root)).
Take an independent set S in v's subtree that is largest among those containing v. No child of v is in S, since each is adjacent to v. For each child u, the part of S inside u's subtree is independent and avoids u, and it must be largest among such sets — otherwise substituting a heavier one gives a heavier S, and the substitution is legal because the subtrees are disjoint and share no edge. Summing gives the first equation.
If S is largest among sets avoiding v, each child is free, and the part of S in u's subtree must be a heaviest independent set there with no constraint, which is max(with(u), without(u)). Again the substitution is legal because distinct subtrees share no vertex and no edge. That disjointness is exactly what a tree provides and a cycle destroys, and it is where the proof would fail on a general graph.
□
The proof is worth reading twice for that last sentence. Optimal substructure here is not a property of the objective; it is a property of the input's shape. The same objective on a graph with one extra edge has no such decomposition, and no amount of care with the recurrence recovers it.
The lab loads a tree on seven vertices: a path 1-2-3-4 with extra leaves hanging off 2, 3 and 4, and weights 1 6 6 6 1 1 1. Vertices 2, 3 and 4 are the heavy ones and they form a path, so at most two of them can be chosen. The pass returns 13, choosing vertices 2, 4 and 6 — two of the three heavy ones and one leaf — and every one of the 128 subsets confirms 13.
The chosen set is tested for independence against the edge list as it was typed, not against the adjacency structure the pass walked. That matters: a bug in building the adjacency map would make the pass and a structure-based check wrong in the same way, and the two would agree. Reading the raw edges is a route that shares nothing with the pass.
Then the set is re-weighed, and its total compared with the number the pass reported. Independence alone is not enough — the empty set is independent — and a matching total alone is not enough either, since a heavier but illegal set would also fail to be an answer. Both checks, separately, and the panel prints both verdicts.
The instinct readers arrive with is to alternate: take every second level. On a path that is right, and the lab ships a path where it gives 15, the correct answer. On this tree, alternating from the root takes vertices 1, 3, 5 and 7 for a total of 9, against the optimum's 13 — and alternating the other way happens to give 13. A rule whose answer depends on which parity you start from is not a rule until that choice is made, and making it correctly is the problem again.
The measured counts are 7 vertex visits and 12 reads for the pass, against 128 subsets for the check, on a tree of seven vertices. The proved bounds are Θ(n) and Θ(2ⁿ n). Here the measurement and the bound agree in order already at n = 7, which is worth stating plainly because on three other pages of this course they do not — the coin table loses to a plain recursion at an amount of six, the chain table loses to enumeration at four matrices, and the last lesson of the course loses by a factor of forty.
Interactive
Two numbers per vertex, one pass, and every subset as the check
Method
The table is still a table; what changes is that the index set and the fill order come from the input.
Two here, because the only thing the parent needs to know about a child's subtree is what it is worth with the child taken and without. If the parent would need to know more, the state is bigger and the pass is more expensive; if it would need to know the whole subtree, there is no dynamic program.
The answer is a property of the tree, not of the root, so any vertex will do. That is worth checking on a small example by re-rooting and re-running, because if it does matter, the state is wrong.
Postorder guarantees every child is finished before its parent, which is exactly the condition the reads need. This is the one lesson on the course where the order cannot be got wrong, and the reason is that the structure supplies it.
Read the edge list as typed rather than the structure the algorithm built. A check that shares a data structure with the thing it checks will agree with it about the bugs they have in common.
The empty set is independent and worth nothing. A set that is independent and adds to the reported total is a checked answer; either check alone is not.
The tree is the path 1-2-3-4 with a leaf 5 on vertex 2, a leaf 6 on vertex 3 and a leaf 7 on vertex 4. Weights are 1, 6, 6, 6, 1, 1, 1. Rooted at vertex 1, the postorder is 7, 4, 6, 3, 5, 2, 1.
Vertex 3 is the interesting line: with and without are both 7. Taking it costs its two children's freedom and gains its own 6; declining it lets vertex 4 take its 6 and vertex 6 take its 1. The tie means the pass could have gone either way at that vertex, and the answer above it is unaffected, which is a reminder that an optimum can be non-unique in shape while being unique in value.
Vertex 1's line shows where the answer comes from: it has weight 1 and one child, so taking it is worth 1 + 8 = 9 and declining it is worth 13. The root is declined, and a reader who expected the root to matter is reading the weight rather than the structure. Switch the lab to the star and the same thing happens for the opposite reason: the centre is worth 3 and the four leaves together are worth 12.
For a faded rehearsal, keep the tree and set every weight to 1 before running it. The supplied first move: with equal weights the problem becomes the largest independent set by count, and the three leaves 5, 6 and 7 are pairwise non-adjacent, so the answer is at least 3. Work out whether it is more, then check — and note that the pass returns a set, not just a count, so you can see which one it picked.
You should be able to choose a state that summarises a subtree in a few numbers, write the pair recurrence, point to the line of the proof that needs disjointness, and check a returned set against the raw input rather than against the algorithm's own scaffolding.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.