Dynamic Programming – 6 : Optimum sum of tree nodes

February 3, 2011 Leave a comment

Optimum sum of tree nodes

We are given a rooted tree T with root r. Each node x has a real value v(x) associated with it. We are to find a subset of nodes of the tree, such the sum of the values of the selected nodes is maximized, subject to the condition that if we choose a node x, we cannot choose any of its children or its parent.

Solution.

Notation. Let OPT (x) denote the optimum value on a sub-tree rooted at node x. Let OPT (1,x) denote the optimum value on a sub-tree rooted at node x subject to the condition that x is selected as part of the optimal subset. Let OPT(0,x) denote the optimum value on a sub-tree rooted at x subject to the condition that x is not selected as part of the optimal subset.

Then, we have that:

OPT(x) = max \{OPT(1,x), OPT(0,x)\}.

OPT(1,x) = v(x) + \sum_y OPT (0,y) (where the summation is over all children y of x.)

OPT(0,x) = \sum_y OPT (y) (where the summation is over all children y of x.)

—

Also, if x is a leaf, then OPT(1,x) = v(x), and OPT(0,x) = 0.

Pseudocode for computing OPT(root)

We can compute OPT(root) in a bottom up fashion starting from the leaves. The recurrence equations for a node x involve the OPT values for its children. Thus, before computing the OPT value for node x, we compute the OPT values for its children.

Let the nodes of the tree be arranged in levels from Level 0 till Level L such that the root is at Level 0.

For i going from L downto 0:

For all nodes x in Level i:

Compute OPT[1,x], OPT[0,x] and OPT[x] using the above recurrence.

Set Soln[x] = 1 if OPT[1,x] >= OPT [0,x]. Else, set Soln[x] = 0.

End.

—-

The above code has a running time of O(n) where n represents the number of nodes in the tree. [ We compute OPT values for n nodes. For each node, we compute the OPT values by summing up the OPT values over all of its children. Aggregating over all nodes, and observing the each node can have at most one parent, we find that the summing up operation costs O(n). Therefore, the total cost is O(n+n) which is O(n). Another way to look at it is that the aggregate cost of the summing up operations over all nodes is O(m) [where m represents the number of edges in the tree], which for a tree is O(n). ]

—-

Computing the optimal subset:

We do so using the Soln[x] values.

Function: Print_Solution (x)

If (Soln[x] == 1)

Print x.

For all grand-children y of x:

Print_Solution (y);

Else

For all children y of x:

Print_Solution (y);

End.

—-

Print_Solution(root) has a running time of O(n).

—-

Filed under other programming, Theoretical Computer Science Tagged with , , ,

Leave a comment