Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that minimize $\sum_i \sigma(i)$. Of course, the problem until now is easy :

  1. If there are only non-negative costs the solution is the empty set.

  2. If there are some non-positive costs, we select them all.

But, there is an additional constraint that states: "if a node $\sigma(i)$ is selected, its predecessor to the root is also selected. Thus we are looking for the set of nodes that grow upward to the root and that minimize that sum, or equivalently, we are looking at a subtree of root $r$ that minimize that sum.

My question is how to design an algorithm that solves this problem and how to prove its correctness and compute its complexity?

(I have a hint that states that we could do some bottom-up traversal, of the tree but I don't know how to use this information)

Any help will be appreciated. Thanks

  • $\begingroup$ Let's call $T(i)$ the best total cost you can achieve if node $i$ is the root of the selected subtree. Then you must find a relation between $T(i)$ and all $T(j)$ with $j$ child of $i$ (this is quite easy). You can finally build either a recursive method starting from root or an itertive one starting from leaves. Be careful, the answer to your question is not $T(root)$ but the best $T(i)$ found in all nodes. $\endgroup$ – Optidad May 17 '19 at 8:12
  • 1
    $\begingroup$ @Vince: I think the answer is $T(root)$ -- the subtrees the OP is optimising over are those that "grow upward" from any chosen set of vertices towards the root. $\endgroup$ – j_random_hacker May 17 '19 at 8:45
  • $\begingroup$ Can you precise to me how to get the $T(root)$ from the relation ? $\endgroup$ – user99918 May 17 '19 at 13:57
  • $\begingroup$ You say "if a node is selected its predecessor is selected" but then you say the problem is to select a subtree. Those two problems are not equivalent. If node $a$ has two children $b,c$, then in the former problem I could select $a+b$ but in the latter I could not. So please decide which problem you are asking about, then edit the question accordingly. $\endgroup$ – D.W. May 17 '19 at 15:48
  • 1
    $\begingroup$ I think you can select a and b and still name it a subtree ! ibb.co/3d7b0P? It's not a binary tree so I can't see why you can't pick only one children ? $\endgroup$ – user99918 May 17 '19 at 22:50

For a node $i$ with children $j_1,\ldots,j_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence $$ \tau(i) = \min(0, \sigma(i) + \tau(j_1) + \cdots + \tau(j_d)). $$ Indeed, there are two cases to consider. Either we take no vertex, in which the answer is 0. Otherwise, we must take $i$ itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of $i$.

Like all such recurrences on trees, this one can be evaluated in linear time in many ways.

  • $\begingroup$ But the constraint des not state that if we chose a node we must choose one of its subtrees, I mean we can still choose a node without choosing any of its childrens. We must chose a parent I think $\endgroup$ – user99918 May 17 '19 at 10:37
  • $\begingroup$ I don’t see how this contradicts my solution. $\endgroup$ – Yuval Filmus May 17 '19 at 10:38
  • $\begingroup$ "Otherwise, we must take i itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of i" $\endgroup$ – user99918 May 17 '19 at 10:39
  • $\begingroup$ I still don’t see the contradiction. A valid solution for each child is to take the empty set. $\endgroup$ – Yuval Filmus May 17 '19 at 10:50
  • $\begingroup$ got it, confused "taking a node" with a solution $\endgroup$ – user99918 May 17 '19 at 12:43

Your Answer

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