[Solved]: Algorithm to find the shortest walk with k leaf nodes on a tree

Problem Detail: 

Let's say I have a general tree. What algorithm can I use to find a shortest walk that starts at the root, passes through exactly $k$ different leaves, and ends at the root? Passing through a node/edge more than once is allowed.

For example, consider this graph:

For $k = 1$, the shortest walk would have the node 4. For $k = 2$, the leaf nodes would be 4 and 12. For $k = 3$, the leaves would be 4, 16 and 17.

What I actually need is the length of the shortest walk (if this simplifies anything).

I could not find an algorithm for this, but maybe I searched with the wrong terms.

Asked By : Victor Gomes

Answered By : Tom van der Zanden

This can be solved by a fairly standard dynamic programming algorithm. For a given node $v$, let $C(v,k)$ be the minimum length of a (closed) walk through the subtree rooted at $v$ passing through exactly $k$ leaf nodes ($C(v,k)=\infty$ if there is no such walk).

If a node $v$ has children $c_1,\ldots c_m$, then $C(v,k) = min_{k=a_1 + \ldots + a_m} \Sigma_{\{i:a_i\not = 0\}} 2 + C(c_i, a_i)$ (i.e. taking the minimum over all ways to split up $k$ over the children of the node).

With some modification, this can be made to run in $O(n^3)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51738

3.2K people like this

 Download Related Notes/Documents