# Algorithm to find the shortest walk with k leaf nodes on a tree

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.

• What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. – D.W. Jan 12 '16 at 0:21

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)$.
• $O(n^2)$? Interesting. – Hendrik Jan Jan 12 '16 at 17:40
• Whoops, now that I think about it I can only do $O(n^3)$, but you definitely don't need to iterate over the exponentially many ways to split up $k$. – Tom van der Zanden Jan 12 '16 at 17:47
• How to achieve $O(n^3)$? – hengxin May 26 '16 at 12:39