4
$\begingroup$

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:

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Jan 12 '16 at 0:21
4
$\begingroup$

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)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ $O(n^2)$? Interesting. $\endgroup$ – Hendrik Jan Jan 12 '16 at 17:40
  • $\begingroup$ 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$. $\endgroup$ – Tom van der Zanden Jan 12 '16 at 17:47
  • $\begingroup$ How to achieve $O(n^3)$? $\endgroup$ – hengxin May 26 '16 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.