[Solved]: Computing maximum-cost subtree that uses at most k edges

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

 Ask a Question

 Download Related Notes/Documents