It should be a very easy question, but I am a little bit confused. According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using Dynamic Programming (the Algorithm is also explained on page 562 of the book Algorithm Design). Now, imagine that we want to trace the algorithm on a random graph like the figure below where the numbers in the balls show the weight. enter image description here

I want to know, does it matter which node I am selecting as the root? Can you please guide me through the steps of this algorithm's tracing on this graph?


It won't matter which node you select as the root, in the sense that the algorithm will always find a maximum-weight independent set. The actual set of nodes selected by the algorithm might differ, if there are multiple maximum-weight solutions.

Let's say the root is the node with weight 2. Either it is in the optimal solution, or it isn't.

  • If it is, then 7, 10, and 7 are not; the remaining tree only contains 4. Thus this solution has weight 2 + 4 = 6.
  • If it is not, then the answer is the maximum-weight independent set on the forest in which the components are the subtrees with weight 7, 10, and (7, 4). Solving the problem recursively on the subtrees gives 7 + 10 + 7 = 24.

Since 24 > 6, the answer is 24.

  • 1
    $\begingroup$ Thank you so much for your very clear explanation. $\endgroup$ – Reza Hadi Dec 5 '18 at 16:07

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.