2
$\begingroup$

I'm looking for an efficient algorithm for the following problem:

Input: a binary, complete tree with a cost on each edge, an integer $k$
Output: the maximum-cost subtree containing $\le k$ edges

For purposes of this problem, a subtree is defined to be a connected subset of edges. Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree.

Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered 1. I read somewhere that it's possible to use a hashing function to compute it, but there was no explanation given.

I would also be interested to learn of an algorithm that works for graphs that aren't just binary trees.

Here's an example, with the desired subtree marked in yellow:

example tree

$\endgroup$
  • $\begingroup$ 1. What do you mean by "only one path originates" [from the root]? That seems like it can't be right -- for instance, there are multiple paths starting from the root in your example, including 1-2-4 and 1-2-3 and more. 2. When you talk about "using a hashing function to compute it", what does "it" refer to? Also can you provide a source for that statement? 3. What approaches have you considered? $\endgroup$ – D.W. Jun 14 '16 at 5:41
4
$\begingroup$

Say our tree is $T = (V, E)$ with weight function $w : E \to \mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges.

There is a $\Theta(nk^2)$-time and $\Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming.

Idea: Store in every node $v$ the maximum weight obtainable using $i \in 1, \dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b_l, k_l)$ and $(b_r, k_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b_l + k_l + b_r + k_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes.

Details:

for v ∈ V {
  for i ∈ [1..k] {
    v.maxWeight[i]   = 0
    v.chooseLeft[i]  = 0
    v.edgesLeft[i]   = 0
    v.chooseRight[i] = 0
    v.edgesRight[i]  = 0
  }
}

globalMax = [null, 0, -1]

def annotate(v) {
  if v is not a leaf {
    annotate(v.left)
    annotate(v.right)

    for i ∈ [1..k] {
      for j ∈ [0..i] {
        w  =   [j > 0]   * w((v, v.left))  + v.left.maxWeight[max(0,j-1)]
             + [i-j > 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)]

        if w > v.maxWeight[i] {
          v.maxWeight[i]   = w
          v.chooseLeft[i]  = min(j,1)
          v.edgesLeft[i]   = max(0,j-1)
          v.chooseRight[i] = min(i-j,1)
          v.edgesRight[i]  = max(0,0-j-1)
        } 
      }

      if v.maxWeight[i] > globalMax[2] {
        globalMax = [v, i, v.maxWeight[i]]
      }
    }
  }  
}

annotate(T.root)

What remains then is to move top-down from globalMax[0] and follow the chooseX[_] links with edgesX[_] to construct the optimal subtree with globalMax[1] edges and weight globalMax[2].

Proof of correctness (by induction) and analysis are elementary.

The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{\operatorname{deg}(v)}$ then, if implemented naively.

$\endgroup$
  • $\begingroup$ Thank you very much for the detailed response, seems much more intuitive now that I see it. Would you be able to comment at all on using a hash function to compute the sub-tree, is it even possible? Otherwise I'll mark it correct if you don't want to edit it. $\endgroup$ – Jakub Kawalec Jun 13 '16 at 16:29
  • $\begingroup$ @JakubKawalec I don't see how a hash function can help with this approach. Were you maybe thinking of compressing trees? If you could track down that reference you mention reading I'd be interested. $\endgroup$ – Raphael Jun 13 '16 at 16:39
  • $\begingroup$ I think it was more in reference to memoization and using a hash table to not recompute best distances everytime. $\endgroup$ – Jakub Kawalec Jun 14 '16 at 8:24
  • $\begingroup$ @Raphael It's actually easy to extend it to higher degree in polynomial time. You basically run a knapsack style algorithm for each node, adding sons iteratively. If you also, while iterating for a certain son's contribution, upper bound this value by the size of its subtree (which is obviously sound), your runtime is bounded by $O(n ^ 2)$, regardless of $K$. $\endgroup$ – Mihai Calancea Jun 14 '16 at 15:14
  • $\begingroup$ @MihaiCalancea You mean you have a linear-time "knapsack style" algorithm at hand? Please give a reference and/or add a new answer detailing this. $\endgroup$ – Raphael Jun 17 '16 at 11:08
3
$\begingroup$

I'll describe an extension of @Raphael's answer for arbitrary trees. It's probably not relevant for OP, but it might be for someone else.

The basic idea is the same. We use dynamic programming and our state is $dp[x][y]$ = optimal cost for acquiring a $y$-edge connected subtree rooted in node $x$. As Raphael stated, for binary trees, it's as simple as iterating over how many edges we take from each subtree:

Edit: These formulas don't account for adding the node-son edges to the answer and possibly other details. The heart of the solution lies in the conceptual approach and is not affected by this.

$dp[x][y] = max(dp[son[x][0]][i] + dp[son[x][1]][y - i], i = 0..y)$

Now, it would seem that if the degree were limited by three, we should iterate over how much we take from each of the first two subtrees. But we don't. Consider the exact same recurrence as a above, with a notational twist.

$dpFirstTwo[x][y] = max(dp[son[x][0]][i] + dp[son[x][1]][y - i], i = 0..y)$

Ok so we've just ignored the third son. To take care of him, we'll do this again, but iterating over how many edges we take from the first two sons combined, which we have stored in $dpFirstTwo$.

So we have:

$dp[x][y] = max(dpFirstTwo[x][i] + dp[son[x][2]][y - i], i = 0..y)$

This can be easily extended. The main idea is that before processing the $i$-th son, we already have computed a, let's call it, $dpFirst(i-1)sons[x][y]$ table. And we can combine these results with the $i$-th son's contribution in an identical manner with the binary tree case.

Also, I claim that the complexity can come down to $O(N ^ 2)$ overall, where $N$ is the vertex count. This is better than $O(N K ^ 2)$ for most $K$'s. To achieve this complexity, you just have to take care and not try to compute or iterate over states that cannot exist: A subtree with $5$ nodes cannot produce a $7$ edge subtree. If you do this, for each node you will do work proportional to the sum of pairwise products of sons subtrees sizes. Because these, in total, amount to all the pairs of nodes in the tree, we obtain the desired $O(N ^ 2)$ bound.

An implementation can be tested here: http://main.edu.pl/en/archive/pa/2007/bar. (You need $O(N ^ 2)$ time for 100 points)

$\endgroup$
  • $\begingroup$ Byteland - OI style description, 32MB memory limit, so familiar. Oh, this is OI indeed. $\endgroup$ – Evil Jun 19 '16 at 18:51
  • $\begingroup$ Hah, indeed :) If by any chance you're not familiar with it, the Polish OI online judge is a wonderful collection of algorithmic tasks! $\endgroup$ – Mihai Calancea Jun 19 '16 at 19:19

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.