**Problem Detail:**

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:

###### Asked By : Jakub Kawalec

#### Answered By : Raphael

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/59580

## 0 comments:

## Post a Comment

Let us know your responses and feedback