Dynamic programming on trees

This site is a tree. Every page has a section: the parent of the address /utilities/math/exams/ent/equations is /utilities/math/exams/ent, its parent is /utilities/math/exams, and so on up to the home page. The sitemap has 8966 pages, and together with twenty sections that have no page of their own, 8986 nodes. Which two pages are furthest apart if you move only by breadcrumbs? From which is everything else closest? Both questions can be answered for all pages at once in two passes over the tree, from the leaves to the root and back.

The most distant pages are 11 clicks apart, and they are one and the same page in two languages: a worked equations problem from the UNT trainer, the Russian and the English version. The English site lives in the /en section, so the English page is one level deeper, and the path between them goes through the home page. The centre of the site is the home page itself: from it any page is on average 3.409 clicks away. Next, two thousandths behind, comes /en: the English half is almost as large as the Russian one.

The idea

Hang the tree from a root. The problem about the subtree of vertex v breaks down into the same problems about the subtrees of its children, and the children’s subtrees do not intersect and are connected by nothing except v itself. So for each vertex keep a few numbers about its subtree, such as its size, its depth, the best answer “with v” and “without v”, and compute them from the children’s numbers. The order is children before parent, that is, from the leaves to the root; each vertex is computed once, and the whole tree in O(n).

This is dynamic programming on trees. In ordinary dynamic programming the order of filling the table has to be invented, but here the tree itself gives it: the reverse order of a breadth-first traversal, or leaving a vertex in a depth-first traversal. The simplest such computation is the size of a section: a vertex’s size is one plus the sizes of its children. That is how du computes the size of a directory on disk.

A step further is the diameter, the longest path in the tree. Every path has a highest vertex where it turns downwards, and from there it descends through two different children. So for each vertex it is enough to know the depths of its two deepest branches through different children: the longest path turning at v is their sum, and the diameter is the largest such sum over all vertices. On the site’s tree it equals 11 and is reached at the home page: six levels down the English branch and five down the Russian one.

An office party without bosses

A classic textbook problem. A company is throwing a party, each employee has a rating of “how much fun they are”, and nobody wants to have fun in front of their direct boss. Whom should be invited to maximise the fun? In graph terms this is the maximum-weight independent set in a tree: no two chosen vertices are joined by an edge.

One number per vertex is not enough: the parent cares whether the child itself is invited. So there are two numbers. take[v] is the best fun of department v if v is invited: its subordinates cannot be invited, and each child contributes its skip. skip[v] is the best if v is not invited: then each child is free, and contributes the better of its two.

The numbers under each person in the scene are this very table. Try the greedy rule “the most fun first”: the director is fun, a 7, and is invited first, after which the three department heads, at 6, 5 and 5, stay at home, and the party scores 13. The table at the director sees both options: 13 with the director, 16 without. In the proof everything rested on the children’s subtrees being independent; in a graph with cycles that is not so, and the maximum independent set problem becomes NP-hard.

Code

The party: the table, reconstructing the guest list from the top down, the greedy rule, and a brute-force check on three hundred random trees.

The guests are reconstructed by a second pass, from the top down: the director decides whether to go by comparing take and skip, and each next person knows whether their boss was invited. If so, they stay at home; if not, they decide the same way for themselves.

The site’s tree: the sizes of sections, the two deepest branches, the diameter, and the sum of distances from each page to all the others.

Rerooting

A pass from the leaves computes the answer for the root. What if the answer is needed for every vertex, as if the tree were hung from it? For example, the sum of distances from a page to all others, to find the centre of the site. You could do n traversals, one from each vertex, but that is n² steps: eighty million on the site’s tree. Instead, notice how the answer changes when the root moves along one edge.

Let total[v] be the sum of distances from v to all vertices, and let c be a child of v with size[c] vertices in its subtree. Moving from v to c, all vertices of the subtree of c become one step closer, and all the others, n − size[c] of them, one step further:

Hence two passes. Bottom up, compute the subtree sizes and total for the root, the sum of depths. Top down, move the root along the edges with the formula above. Both passes are O(n). These two waves are exactly what the “centre” mode of the scene shows: first the pass from the leaves, then from the root, and the vertices are coloured by the sum found.

Not every answer moves over so simply. If what is needed is not a sum but the distance to the farthest vertex, then when moving from v to c the deepest branch of v may go precisely through c, and then it cannot be used. So each vertex keeps its two best branches through different children, the same trick as for the diameter. That is the second problem below.

What it costs

Each vertex is processed once per pass, and a constant is spent per edge: O(n) time and O(n) memory for the vertices’ numbers. If there are more numbers per vertex, for example in a “knapsack on a tree”, where a vertex gets a whole row of a table, the time grows with them, but the traversal order is the same.

The slope for a traversal from each vertex is 2, for rerooting 1. On two thousand vertices Python spends almost 0.4 seconds on the traversals, while rerooting gets through a million vertices faster than the traversals get through two thousand.

When a tree is not a tree

Everything rests on one property: the children’s subtrees are connected to the rest of the tree only through the parent. Add one extra edge, between the sales department and the warehouse, and the warehouse’s take starts to depend on whether the head of sales was invited. A table over subtrees cannot see that.

Sometimes a small extension of the state saves the day. If there are few extra edges, you can enumerate what happens at their ends and solve the problem on a tree for each option. If a graph is “tree-like”, if it can be cut into small pieces, bags, arranged in a tree, the dynamic programming runs over this decomposition tree, and the state stores what is chosen in the current bag: this is already bitmask dynamic programming, and the time grows exponentially only in the size of a bag. This is exactly how the maximum independent set is found on such graphs.

The second trap is the order of children. If the answer depends on the order in which a vertex’s children are visited, for example when the children have to be lined up at the least cost, each vertex has to solve its own small ordering problem, and the time stops being linear. In this article’s problems the order of children does not matter: sums and maximums do not depend on it.

Where it works

Files and directories. A directory’s size is the sum of the sizes of what is nested in it: du computes it in a bottom-up pass. The same pass answers how many files a section holds and how deep the longest nesting goes.

Compilers. How many processor registers are needed to evaluate an expression without saving intermediate values to memory? In 1970 Ravi Sethi and Jeffrey Ullman labelled the expression tree from the bottom up: a node’s number comes from the numbers of its two subtrees, and then code is generated from the labelling, evaluating the “heavier” subtree first.

Biology. If the evolutionary tree of species is known, and the gene letters of the leaves, the living species, are known, then the smallest number of mutations that explains these letters is computed in a pass from the leaves to the root. Walter Fitch described this computation in 1971; at its heart is the same question as in the party problem: what do you need to know about a subtree to decide for the parent.

Olympiads. The maximum independent set, vertex cover, dominating set, diameter, centre, knapsack on a tree. On general graphs the first three are NP-hard, while on trees they are solved in linear time by dynamic programming over subtrees.

Problems

The first is the smallest number of guards who can see all the passages of an exhibition: a vertex cover of a tree, two numbers per hall, and a traversal without recursion on an enfilade of two hundred thousand halls. The second is, for every page of the site, the number of clicks to the farthest one: rerooting, where one best branch is not enough.