Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having

  • $k$ elements
  • no node being an ancestor of another
  • maximal sum of the weights (among all subsets fulfilling the previous two conditions)

Edit: Comments suggest dynamic programming. Here's my failing attempt in that: sort the nodes according to weight in decreasing order. The case $k=1$ is easy of course. Take the first node. But what about moving from $k$ to $k+1$? We can't just take the next weightiest node that is not an ancestor or a grandchild of any of the nodes in the previously constructed subset and add it to the subset. This could fail already in the case $k=1$. What's the correct approach here?

  • 1
    $\begingroup$ This is a standard exercise. What did you try? Where did you get stuck? I suggest you try dynamic programming; we have some guidance on how to approach those problems here. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 27 '18 at 15:03
  • $\begingroup$ Use dynamic programming to get an $O(kn)$ algorithm. (There might be more efficient solutions.) $\endgroup$ – Yuval Filmus Mar 27 '18 at 15:16
  • $\begingroup$ @Yuval Thank you for the suggestion. I already had thought about using DP but really could not get anywhere with that. I described my failed attempt in an edit. Any further hints, please? $\endgroup$ – happyEddie Mar 27 '18 at 15:42
  • $\begingroup$ Try again, this time without sorting the nodes. There are usually many candidate ways you could decompose into subproblems. Try a different decomposition into subproblems. If your first try fails, don't give up -- try to look for a different decomposition. At the links I gave you, you can find a systematic way to identify candidate decompositions to try. $\endgroup$ – D.W. Mar 27 '18 at 15:42
  • $\begingroup$ @D.W. Thanks for the nudge to the right direction. I still have to work out the details to be sure that it really does the job but I think the correct DP approach in each round of $k$ is to work from the leaves upwards and to solve the problem for each subtree. It really helps to know you are on the right path to the solution so that you are not looking for something that does not exists. $\endgroup$ – happyEddie Mar 27 '18 at 17:23

Your Answer

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

Browse other questions tagged or ask your own question.