Finding the heaviest length-constrained path in a weighted Binary Tree

Question

UPDATE

I worked out an algorithm that I think runs in O(n*k) running time. Below is the pseudo-code:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -∞
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-∞);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0;

    // fill our matrix by traversing the tree
    traverseToFillMatrix( T.root, k );

    // consider a path that would arc over a node
    globalMaxWeight = -∞;
    findArcs( T.root, k );

    return globalMaxWeight
end routine


// node = the current node; k = the path length; node.lc = node’s left child; 
// node.rc = node’s right child; node.idx = node’s index (row) in the matrix; 
// node.lc.wt/node.rc.wt = weight of the edge to left/right child;
routine traverseToFillMatrix( node, k )

   if (node == null) return;

   traverseToFillMatrix(node.lc, k ); // recurse left
   traverseToFillMatrix(node.rc, k ); // recurse right

   // in the case that a left/right child doesn’t exist, or both,
   // let’s assume the code is smart enough to handle these cases
   matrix[ node.idx ][ 1 ] = max( node.lc.wt, node.rc.wt );


   for i = 2 to k {
       // max returns the heavier of the 2 paths
       matrix[node.idx][i] = max( matrix[node.lc.idx][i-1] + node.lc.wt, 
                                  matrix[node.rc.idx][i-1] + node.rc.wt);
   }

end routine



// node = the current node, k = the path length
routine findArcs( node, k ) 

    if (node == null) return;

    nodeMax = matrix[node.idx][k];
    longPath = path[node.idx][k];

    i = 1;
    j = k-1;
    while ( i+j == k AND i < k ) {

        left = node.lc.wt + matrix[node.lc.idx][i-1];
        right = node.rc.wt + matrix[node.rc.idx][j-1];

        if ( left + right > nodeMax ) {
            nodeMax = left + right;
        }
        i++; j--;
    }

    // if this node’s max weight is larger than the global max weight, update
    if ( globalMaxWeight < nodeMax ) {
        globalMaxWeight = nodeMax;
    }

    findArcs( node.lc, k ); // recurse left
    findArcs( node.rc, k ); // recurse right

end routine

Let me know what you think. Feedback is welcome.

---

I think have come up with two naive algorithms that find the heaviest length-constrained path in a weighted Binary Tree. Firstly, the description of the algorithm is as follows: given an n-vertex Binary Tree with weighted edges and some value k, find the heaviest path of length k.

For both algorithms, I'll need a reference to all vertices so I'll just do a simple traversal of the Tree to have a reference to all vertices, with each vertex having a reference to its left, right, and parent nodes in the tree.

Algorithm 1 For this algorithm, I'm basically planning on running DFS from each node in the Tree, with consideration to the fixed path length. In addition, since the path I'm looking for has the potential of going from left subtree to root to right subtree, I will have to consider 3 choices at each node. But this will result in a O(n*3^k) algorithm and I don't like that.

Algorithm 2 I'm essentially thinking about using a modified version of Dijkstra's Algorithm in order to consider a fixed path length. Since I'm looking for heaviest and Dijkstra's Algorithm finds the lightest, I'm planning on negating all edge weights before starting the traversal. Actually... this doesn't make sense since I'd have to run Dijkstra's on each node and that doesn't seem very efficient much better than the above algorithm.

So I guess my main questions are several. Firstly, do the algorithms I've described above solve the problem at hand? I'm not totally certain the Dijkstra's version will work as Dijkstra's is meant for positive edge values.

Now, I am sure there exist more clever/efficient algorithms for this... what is a better algorithm? I've read about "Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees" but that is really complicated and I don't understand it at all. Are there other algorithms that tackle this problem, maybe not as efficiently as spine decomposition but easier to understand?

Answer 1

You could use a DFS downwards from each node that stops after k edges to search for paths, but notice that this will do 2^k work at each node for a total of O(n*2^k) work, since the number of paths doubles at each level you go down from the starting node.

As DasBoot says in a comment, there is no advantage to using Dijkstra's algorithm here since it's cleverness amounts to choosing the shortest (or longest) way to get between 2 points when multiple routes are possible. With a tree there is always exactly 1 way.

I have a dynamic programming algorithm in mind that will require O(nk) time. Here are some hints:

• If you choose some leaf vertex to be the root r and direct all other vertices downwards, away from the root, notice that every path in this directed tree has a highest node -- that is, a unique node that is nearest to r.
• You can calculate the heaviest length-k path overall by going through each node v and calculating the heaviest length-k path whose highest node is v, finally taking the maximum over all nodes.
• A length-k path whose highest node is v must have a length-i path descending towards one child and a length-(k-i) path descending towards the other.

That should be enough to get you thinking in the right direction; let me know if you need further help.

Answer 2

Here's my solution. Feedback is welcome.

Lets treat the binary tree as a directed graph, with edges going from parent to children. Lets define two concepts for each vertex v:

a) an arc: which is a directed path, that is, it starts from vertex v, and all vertices in the path are children of the starting vertex v.

b) a child-path: which is a directed or non-directed path containing v, that is, it could start anywhere, end anywhere, and go from child of v to v, and then, say to its other child. The set of arcs is a subset of the set of child-paths.

We also define a function HeaviestArc(v,j), which gives, for a vertex j, the heaviest arc, on the left or right side, of length j, starting at v. We also define LeftHeaviest(v,j), and RightHeaviest(v,j) as the heaviest left and right arcs of length j respectively.

Given this, we can define the following recurrences for each vertex v, based on its children:

LeftHeaviest(v,j) = weight(LeftEdge(v)) + HeaviestArc(LeftChild(v)),j-1);
RightHeaviest(v,j) = weight(RightEdge(v)) + HeaviestArc(RightChild(v)),j-1);
HeaviestArc(v,j) = max(LeftHeaviest(v,j),RightHeaviest(v,j));

Here j here goes from 1 to k, and HeaviestArc(v,0)=LeftHeaviest(v,0),RightHeaviest(v,0)=0 for all. For leaf nodes, HeaviestArc(v,0) = 0, and HeaviestArc(v,j)=-inf for all other j (I need to think about corner cases more thoroughly).

And then HeaviestChildPath(v), the heaviest child-path containing v, can be calculated as:

HeaviestChildPath(v) = max{ for j = 0 to k LeftHeaviest(j) + RightHeaviest(k-j)}

The heaviest path should be the heaviest of all child paths.

The estimated runtime of the algorithm should be order O(kn).