Trouble understanding this dynamic programming solution

Question

Here is the question:

I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.

for example: If n=3 and k=1

and the given tree is 1---2---3

Then the total valid subtrees would be 6

{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}

I know I can enumerate all 2^n trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in n? Something close to O(n^3) or even O(n^4) would be nice.

for k=1 this value turns out to be 2*n

There was a solution provided for this one as:

This is a fairly typical instance of the DP-on-a-tree paradigm. Let's generalize the problem slightly by allowing the specification of a root vertex v and stratifying the counts of the small-boundary trees in two ways: whether v is included, and how many edges comprise the boundary.

The base case is easy. There are no edges and thus two subtrees: one includes v, the other excludes v, and both have no boundary edges. Otherwise, let e = {v, w} be an edge incident to v. The instance looks like this.

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Compute recursively the stratified counts for L rooted at v and R rooted at w.

Subtrees that include v consist of a subtree in L that includes v, plus optionally e and a subtree in R that includes w. Subtrees that don't include v consist of either a subtree in L that doesn't include v, or a subtree in R (double counting the empty tree). This means we can obtain the stratified counts by convolving the stratified counts for L with the stratified counts for R.

Here's how this works on your example. Let's choose root 1.

  e
1---2---3

We choose e as shown and recurse.

1

The vector for includes-1 is [1], since the one subtree is {1}, with no boundary. The vector for excludes-1 is [1], since the one subtree is {}, also with no boundary.

2---3

We compute 2 and 3 as we did for 1. The vector for includes-2 is [1, 1], since {2, 3} has no boundary edges, and {2} has one. We obtained this vector by adding the includes-2 vector for 2, shifted by one because of the new boundary edge to make [0, 1], to the convolution of the includes-2 vector for 2 with the includes-3 vector for 3, which is [1, 0]. The vector for excludes-2 is [1] + [1, 1] - [1] = [1, 1], where [1, 1] is the sum of the shifted includes-3 vector and the excludes-3 vector, and the subtraction is to compensate for double-counting {}.

Now, for the original invocation, to get the includes-1 vector, we add [0, 1], the includes-1 vector for 1 shifted by one, to the convolution of [1] with [1, 1], obtaining [1, 2]. To check: {1, 2, 3} has no boundary, and {1} and {1, 2} have one boundary edge. The excludes-1 vector is [1] + [1, 2, 1] - [1] = [1, 2, 1]. To check: {} has no boundary, {2, 3} and {3} have one boundary edge, and {2} has two boundary edges.

I am unable to understand this fully. Can anyone help?

Answer 1

The problem is to count the subtrees of an undirected tree that have at most k outgoing edges to the rest of the tree.

The idea of the algorithm is a divide and conquer plus dynamic programming technique. For a tree T, you divide it into 2 subtrees, and for each you compute all subtrees that have i outgoing edges for each i less than or equal to k. There is however a little twist to allow the recurrence step to work. The divide and conquer part is not really necessary, but it does allow a simpler organization.

---

I agree that the explanation of the algorithm that you were given is somewhat obfuscated.

small-boundary trees are what you called valid trees, with at most k out-going edges.

Consider your tree T.

Though in your undirected tree T all nodes are born equal, you choose to distinguish a root v.

The idea is to count the number of subtrees for each value of the number of outgoing edges, an also separate those that contain the root v from those that do not.

Hence you have two vectors Tv+ and Tv--, for the subtrees including v and for the subtrees not including root node v. Tv+[i] is the number of subtrees including V that have i outgoing edges. Tv-[i] is the number of subtrees not including V that have i outgoing edges.

The sum of these two vectors will give you the number of subtrees with i outgoing edges for each value of i less than or equal to k. At this point the distinction into two vectors has not been useful, but it is needed for the recursion.

Before using them, you have to compute these two vectors.

For that purpose, you choose an edge e={v,w}, which cuts your tree T in two subtrees L and R, respectively rooted in v and w as shown on the figure

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Suppose you have computed the vectors Lv+, Lv-, Rw+ and Rw-, then you can use the results in those 4 vectors to compute Tv+ and Tv- as explained in the document.

Subtrees that include v consist of a subtree in L that includes v, plus optionally e and a subtree in R that includes w.

translates into :

Tv+[i] = Lv+[i-1] + sum (Lv+[j] * Rw+[k]) for all (j,k) such that j+k=i , for i>0

Tv+[0] = 1 Only the whole tree T contains v and has no outgoing edges.

The i-1 in Lv+[i-1]is to account for the added outgoing edge {v,w}

The sum of products is for all subtrees that include the edge {v,w}, and thus have a part in L and another in R.

Subtrees that don't include v consist of either a subtree in L that doesn't include v, or a subtree in R (double counting the empty tree).

translates into :

Tv-[i] = Lv-[i] + Rw+[i-1] + Rw-[i] for i>0

Tv-[0] = 1 for th empty tree {}

The i-1 in Rw+[i-1] is for the fact that subtrees counted in Rw+ get an extra edge {v, w} in the recurrence step since v is not included

There is empty tree in Lv-[i] and another in Rw-[i], but it does not matter as empty trees are considered in the case i=0.

hoping I did not miss anything.

Is this enough to get you started, or do you need more?

One last point. The description of the algorithm starts by saying that it will consider the count of small-boundary trees, which I believe are your valid trees. If you know in advance the value of k (defining them) that you do not wish to exceed, then you vectors need only have length k+1. For example, if k=1, the vectors should be of length 2 (for zero edges and for 1 edge). Any subtree that exceeds k edges will be useless for the rest of the algorithm (the count cannot go down) and can thus be forgotten.

Note that, as described, the original algorithm uses variable size arrays, only as long as needed for the subtree at hand. That is required if you do not fix k in advance. If you do, you just use length k+1 as I said.

But this is a personnal remark that you may or may not trust. It is not in the algorithm you have been given.