# Minimum-average-cost subtree that is not necessarily spanning

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

Input: a rooted tree (undirected) with a cost on each edge. It could be considered directed away from the root (or towards the root).

Output: a subtree from the root that has the minimum average cost per edge.

There are some results for minimum average-cost spanning trees, but in this case the output is not necessarily spanning.

In the tree below, where A is the root of the tree:

1. The subgraph containing nodes A and B has average cost mean(6) = 6
2. We can improve on the average cost by including node C to get mean(6, 5) = 5.5.
3. The optimal subgraph includes nodes A, B, D and E, but not C, to get mean(6, 7, 1) = 4.67

A greedy algorithm would be a depth-first search that appends edges that lower the mean. But such an algorithm would miss the optimal subgraph, because it wouldn't append the edge to node D with cost 7.

• Is the root given as part of your input? If so, the edges can be considered to be directed away from the root. Also it sounds like your input is simply a (possibly rooted) tree, right? Writing "minimum spanning tree" implies there is some meaningful underlying graph that is relevant somehow, but IIUC that's not the case here. – j_random_hacker Apr 24 '20 at 18:34
• Also: What is a single-vertex, no-edge tree considered to cost? – j_random_hacker Apr 24 '20 at 18:37
• The root is given as part of the input, and a single-vertex no-edge tree isn't a valid result, at least one edge directly connected to the root has to be included. If the "minimum spanning tree" is irrelevant then I'll remove it, thanks for pointing that out. – nacnudus Apr 24 '20 at 19:18
• Thanks for fixing that. This is actually a very interesting problem :) – j_random_hacker Apr 25 '20 at 10:40
• I can think of an $O(n^2)$-time-and-space DP algorithm that in effect computes the minimum possible weight sum of a rooted tree having exactly $i$ edges for each $i < n$, by first transforming the input tree into a binary tree with a second, "real edge or not", edge weight in $\{0,1\}$ on each edge. But this does not make any use of properties of averages -- it would work for optimising any function of the sum and edge count -- so it might be that there is a faster algorithm out there. – j_random_hacker Apr 25 '20 at 11:17

@j_random_hacker I was thinking along similar lines to DP (a recursive algorithm that ran through the subtrees out to the leaves) but I hit a problem - I don't think the problem has an optimal substructure.

If you consider the graph in the image below, if x=1 then the 30-weight-edge is not part of the optimal solution (100,1,1,1) whereas if x=40 then it is (100,1,1,30). Inclusion of a specific edge in the optimal solution depends upon the weight of edges in completely separate parts of the graph.

I'd actually started writing some code before I realised. My recursive function assumed that given a subtree & the path from root to subtree you could make a decision but this counterexample broke it :(

• This is the point at which I gave up too. Thank you for making this example. – nacnudus Apr 26 '20 at 17:14
• Right, it unfortunately doesn't have optimal substructure. The $O(n^2)$ algorithm I sketched in a comment does though: The idea is to solve $n$ separate problems, where in the $i$-th problem we are looking for the largest sum (not average) but have the constraint that we must use exactly $i$ edges. Then in a final pass we loop through these optimal sums, and divide the $i$-th by $i$ to compute the optimal average under the constraint of using exactly $i$ edges, finally returning the best among these averages. – j_random_hacker Apr 26 '20 at 18:07
• I like the concept of changing it into n simpler problems but I still can't see the solution (I'm probably being dense). Finding the largest sum with the constraint of exactly i edges still seems difficult. A greedy algorithm won't necessarily find the optimal solution (where some very low value edges are "behind" a high value edge). And it still doesn't seem to have optimal substructure to use DP. In the example above, when i=4, whether the best solution contains the 30-edge still depends on the value of x Feel like I'm missing something obvious... – bsg42 Apr 27 '20 at 14:12
• [Deleted the original comment, which had the DP wrong] Don't worry, the $O(n^2)$ algorithm isn't obvious! The only way I know to solve it "efficiently" (quadratic time) is on binary trees -- but fortunately trees with vertices having more children can be transformed into binary trees (I'll describe this shortly). Let $f(u,i)$ be the maximum sum of any subtree rooted at $u$ and containing exactly $i$ edges, including the edge from $u$ to its parent, having weight $w_u$. Then $f(u,0)=0$ and $f(u,i>0)=w_u+\max_{0\le j<i}(f(v,j)+f(x,i−j-1))$, where $v$ and $x$ are $u$'s 2 children. – j_random_hacker Apr 30 '20 at 16:26
• (I.e., we partition the budget of $i$ edges between the two child subtrees in all possible ways, and pick the best.) To convert a non-binary tree into a binary tree, imagine taking each non-binary vertex with its children laid out left-to-right: Make the leftmost 2 children the children of a new binary node, then make that node and the third-leftmost original child into the children of a new binary node, etc. This does introduce "imaginary" edges, which complicates the DP -- but only slightly. I'm working on writing up my $O(n\log n)$ algorithm but there are a few details I need to get right. – j_random_hacker Apr 30 '20 at 16:26

## An exact but somewhat complicated $$O(n\log n)$$ algorithm

This problem intrigued me, and the solution I've come up with uses a strategy that's totally new to me (I doubt it's new to the world -- if anyone knows of other problems that can be solved "this way", let me know!). This algorithm allows negative and/or fractional edge costs, and operates directly on trees that may be non-binary. To get the time complexity down to $$O(n\log n)$$ requires making use of a property of averages, as well as a way to efficiently add "blocks" of edges at a time.

Let the input tree be $$T$$, and the parent of a vertex $$v$$ be $$p(v)$$. I will call a subtree of $$T$$ rooted at some node $$v$$ and including the edge $$p(v)v$$ a branch, and say that it is headed by $$p(v)v$$. (Note that a branch headed by $$uv$$ need not include all descendants of $$v$$.) Denote by $$A(G)$$ the average of all edges in the graph $$G$$.

## Combining averages

Lemma 1: The average of the union of two multisets is between the original two averages.

Proof: Suppose multiset 1 has $$b$$ items, which sum to $$a$$, and multiset 2 has $$d$$ items, which sum to $$c$$. Then the average of multiset 1 is $$a/b$$, the average of multiset 2 is $$c/d$$, and the average of their union is $$(a+c)/(b+d)$$. We want to show that the last expression is between the first two.

Suppose w.l.o.g. that $$a/b \le c/d$$. Then:

$$a/b \le c/d\\ ad \le bc\\ ad+ab \le bc+ab\\ a(b+d) \le b(a+c)\\ a/b \le (a+c)/(b+d)$$

Similar reasoning shows that $$(a+c)/(b+d) \le c/d$$.

The utility of this is that it allows us to be certain that adding a multiset to another multiset with a higher average "pulls down" the latter multiset's average, without having to know anything about the items in either multiset or even their sizes.

## Stragegy: Greedy, but not using the raw edge costs

The key to enabling a correct greedy algorithm is the following lemma. The statement is rather convoluted, but in essence it means, "Whenever an optimal solution includes some branch, it must also include every branch with a lower average that could have been added to it at some point".

Lemma 2: Suppose there is an optimal solution $$OPT$$ that contains an edge $$uv$$. Call the branch in $$OPT$$ headed by $$uv$$ $$b_{uv}$$. Then this optimal solution must also include every edge $$xy$$ such that $$x$$ is in $$OPT$$, is not within the subtree of $$T$$ rooted at $$v$$, and there exists a branch $$b_{xy}$$ in $$T$$ headed by $$xy$$ with lower average, i.e., such that $$A(b_{xy}) < A(b_{uv})$$.

Proof: Suppose (towards contradiction) that an optimal solution $$OPT$$ does exist that contains some edge $$uv$$ heading a branch $$b_{uv}$$, but does not contain some edge $$xy$$ for which there exists a branch $$b_{xy}$$ in $$T$$ such that $$A(b_{xy}) < A(b_{uv})$$.

Let $$r$$ be what is left of $$OPT$$ if we remove $$b_{uv}$$. It must be that $$A(r) \ge A(b_{uv})$$, since otherwise we could remove $$b_{uv}$$, and by Lemma 1 obtain a new solution with strictly lower average, contradicting the optimality of $$OPT$$. Thus, again by Lemma 1, $$A(OPT) = A(r \cup b_{uv}) \ge A(b_{uv})$$.

$$A(b_{xy}) < A(b_{uv})$$ by assumption, and the preceding sentence establishes $$A(b_{uv}) \le A(OPT)$$, so combining these we have $$A(b_{xy}) < A(OPT)$$. So by Lemma 1 again, we get that $$A(OPT \cup b_{xy}) < A(OPT)$$, contradicting the optimality of $$OPT$$. Thus $$xy$$ must also be part of this solution.

What this means is that we never need to consider adding an edge to the solution until we have already added every edge that leads to a lower-average branch. IOW, at each step as we are building the solution tree, from among the "frontier" of edges that are adjacent to vertices already in the solution, the only edge we need to consider adding is the one that leads to the subtree having the minimum average. This also makes the stopping criterion clear: Stop as soon as the minimum-attainable-average rises above the average of the solution we have built so far. (Once the minimum is too high to be useful, every other edge surely is too.)

## Computing the minimum averages efficiently with "blocks"

So what we need is a way to efficiently compute, for each edge $$uv$$ in $$T$$, the minimum average of any branch in $$T$$ that is headed by $$uv$$. Once we have these, we can repeatedly pick the lowest-minimum-average edge from a heap, add it to the current solution, and then add all of its child-edges to the heap, continuing until the lowest minimum-average edge exceeds the current solution average.

This is starting to look like a nicer problem: These minimum-average values depend only on the tree below the edge under consideration, suggesting a bottom-up computation might work. It does, but we need to be careful to avoid the time complexity blowing back up to $$O(n^2)$$.

The straightforward approach would be: For each edge $$uv$$ in a postorder traversal, create a new solution containing just that edge, add all of the (already-computed) minimum averages of its child edges to a heap, choose the lowest, add it to the solution and add its own child edges to the heap, and repeat until the stopping criterion is met. This is a correct algorithm, but the problem is that it may be necessary to add $$O(n)$$ edges separately for each starting edge $$uv$$, leading to $$O(n^2)$$ time overall. For example this is true of any tree in which every edge costs less than its parent, since in this case the optimal solution for each starting edge $$uv$$ winds up including every edge in the subtree below it, each of which are added separately.

Instead, once we have discovered all the edges of an optimal branch headed by $$uv$$, we can collapse all of $$v$$'s descendants in this branch into $$v$$, which acquires as children all children of those original vertices. $$v$$ now represents a solid subtree "block" that is never split apart by later algorithm steps, and which can be added in a single step. (The original subtree structure can be stowed away inside $$v$$ to enable the top-level solution subtree to be recursively "exploded" back out once the algorithm is finished.)

## Exotic heaps to the rescue

An edge is only ever collapsed at most once throughout the course of the whole algorithm, and collapsing an edge can be done in $$O(1)$$ time, so there are no efficiency concerns there. But there remains the issue of uncollapsed child edges: These may need to be considered for addition into the solution multiple times, potentially once per ancestor. Or do they? The only way we "consider" these edges is by selecting the one having minimum average value among all frontier edges, and a heap can do this in $$O(\log n)$$ time. So the only remaining issue is ensuring that, when we select an edge to add to the solution and want to add all of its child edges to the heap, this can be done efficiently. This is a heap meld operation, and while it can't be done efficiently by the "standard" binary heap, other heap data structures can accomplish this in as little as $$O(1)$$ amortised time!

It turns out that there's a linear time algorithm, published in Carlson J., Eppstein D. (2006) The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems. In: Arge L., Freivalds R. (eds) Algorithm Theory – SWAT 2006. SWAT 2006. Lecture Notes in Computer Science, vol 4059. Springer, Berlin, Heidelberg.

The paper is paywalled, so I have implemented it in R package called wmms.

Here is a summary of the steps:

1. Guess what the maximum average profit is by using the median.
2. Depth-first (start at some leaves and work in) add the profit and cost of each leaf to its parent, unless profit/cost is lower than the guessed maximum, in which case skip it.
• For non-leaf nodes, use the (sum profit)/(sum cost) of leaves added (aka merged) to it.

The insight behind (1) and (2) is that, if the guess (the median) is correct, then the (sum profit) / (sum cost) will be the maximum.

• Because leaf nodes with lower-than-maximum profit should always be cut.

• And because parent nodes with lower-than-maximum profit should only be kept when their average over the subtree beneath them brings them to/above the maximum.

After this first pass, whatever (sum profit) / (sum cost) is at the root node is now a lower bound on the maximum. And if (sum profit) / (sum cost) is less than the guessed maximum, then the guessed maximum is an upper bound, otherwise the upper bound is Inf, because, as above, if the guessed maximum were correct, then (sum profit) / (sum cost) would have met it.

Before repeating (2) we can prune the tree in a few safe ways.

1. Prune any leaf nodes (or nodes that become leaves by the time they are traversed) whose profit/cost is less than the lower bound that we just defined.
2. Any node (not only leaves) with personal profit/cost (not including remaining child nodes) above the upper bound can be merged with its parent. When merging a non-leaf node with its parent, the non-leaf node's children become direct children of the non-leaf node's parent.

These work because we now know that these nodes are either definitely not in the optimum tree, or definitely are.

The other thing we can do is:

1. Any non-leaf node with profit/cost below the lower bound, and that only has one child, merge the child into it. Because the child has a profit/cost between the bounds, so we don't know yet know if we can drop it, but if we do eventually drop it, we'll definitely drop its parent too. So they might as well be combined. If they aren't eventually dropped, it's because their (sum profit)/(sum cost) meets/exceeds the maximum. We can only do this with only-children, because for siblings, we would need to know the effect of pruning each one without the other.

Now we are ready to repeat (2) to (4).

Eventually, only the root node will remain. Its (sum profit) / (sum cost) will be the maximum.

• It's not clear to me how this achieves $O(n)$ time, but (as with all Eppstein's algorithms) very cool nonetheless! – j_random_hacker Oct 3 '20 at 13:23
• It only finds the minimum average cost of the root. To find the costs of all the nodes, you have to recurse, which presumably is where $O(n)$ breaks down, but I also don't follow their reasoning. – nacnudus Oct 4 '20 at 18:42