Dynamic Programming Help: Binary Tree Cost Edge

Question

Given a binary tree with n leaves and a set of C colors. Each leaf node of the tree is given a unique color from the set C. Thus no leaf nodes have the same color. The internal nodes of the tree are uncolored. Every pair of colors in the set C has a cost associated with it. So if a tree edge connects two nodes of colors A and B, the edge cost is the cost of the pair (A, B). Our aim is to give colors to the internal nodes of the tree, minimizing the total edge cost of the tree.

I have working on this problem for hours now, and haven't really come up with a working solution. Any hints would be appreciated.

Can I ask where is this problem taken from? Is it from any active algorithm competition? — Boris Strandjev
Ok then I would love to try helping you. Can you give any insense of the restrictions of the task? How many colors are there at your disposal? how many nodes you have in the tree. — Boris Strandjev
Thanks :) There are no restrictions. Just n nodes and C colors. The tree is binary, and it can have any structure. All the leaf nodes have to be different colors. Those are the only restrictions of the alg. — Catie
If you want to use dyunamic programming, the question to ask is probably: "assume we have optimally painted a subtree; if we attach this subtree to a parent, how do we color the parent and update the subtree to maintain optimality ?" - Same question for a parent of two sons. And when you attach a subtree to a parent, how deep do you have to update the subtree ? — Yves Daoust

Boris Strandjev Boris Strandjev · Accepted Answer · 2012-02-17T10:19:12

I am going to solve the problem with pseudocode, because I tried writing explanation and it was completely not understandable even for me. Hopefully the code will do the trick. The complexity of my solution is not very good - memory an druntime in O(C^2 * N).

I will need couple of arrays I will be using in dynamic approach to your task:
dp [N][C][C] -> dp[i][j][k] the maximum price you can get from a tree rooted at node i, if you paint it in color j and its parent is colored in color k
maxPrice[N][C] -> maxPrice[i][j] the maximum price you can get from a tree rooted in node i if its parent is colored in color j
color[leaf] -> the color of the leaf leaf
price[C][C] -> price[i][j] the price you get if you have pair of neighbouring nodes with colors i and j chosenColor[N][C] -> chosenColor[i][j] the color one should choose for node i to obtain maxPrice[i][j]

Lets assume the nodes are ordered using topological sorting, i.e we will be processing first leaves. Topological sorting is very easy to do in a tree. Let the sorting have given a list of inner nodes inner_nodes

for leaf in leaves:
   for i in 0..MAX_C, j in 0..MAX_C
       dp[leaf][i][j] = (i != color[leaf]) ? 0 : price[i][j]
   for i in 0..MAX_C,
       maxPrice[leaf][i] = price[color[leaf]][i]
       chosenColor[leaf][i] = color[leaf]
for node in inner_nodes
   for i in 0..MAX_C, j in 0..MAX_C
       dp[node][i][j] = (i != root) ? price[i][j] : 0
       for descendant in node.descendants
           dp[node][i][j] += maxPrice[descendant][i]
   for i in 0...MAX_C
       for j in 0...MAX_C
         if maxPrice[node][i] < dp[node][j][i]
             maxPrice[node][i] = dp[node][j][i]
             chosenColor[node][i] = j

for node in inner_nodes (reversed)
   color[node] = (node == root) ? chosenColor[node][0] : chosenColor[node][color[parent[node]]

Dynamic Programming Help: Binary Tree Cost Edge

2 Answers