patternMinor
Algorithm to find the shortest walk with k leaf nodes on a tree
Viewed 0 times
nodestheshortestwithalgorithmleafwalkfindtree
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#51738, answer score: 4
Revisions (0)
No revisions yet.