1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you so much for your very clear explanation. $\endgroup$ – user94082 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