# Minimize max subtree weight among spanning trees

Suppose we have an undirected, connected graph $$G$$ where vertices have positive integer weights. Let $$\bar{v}$$ be a given vertex in $$G$$. Take a spanning tree $$T$$ of $$G$$ rooted at $$\bar{v}$$ and define its cost as the maximum total weight among all proper subtrees. (Since weights are positive the proper subtree(s) with maximum total weight will be rooted at children of $$\bar{v}$$.) Is there an efficient algorithm to determine the minimum cost over all spanning trees $$T$$?

Some motivation: Imagine vertices are cities, weights are population, edges are roads. Everyone wants to travel to $$\bar{v}$$. A spanning tree is a way of telling people what path to take. The cost of a spanning tree is the max possible traffic on any one road into $$\bar{v}$$.

• Are you looking for a heuristic or do you want an algorithm to give the exact optimal solution? A plausible heuristic is to delete all edges out of $\bar{v}$, start $k$ copies of Prim's algorithm running in parallel, one per neighbor of $\bar{v}$, and schedule them so that at each step you are running whichever copy has the lowest total cost so far; and never selecting any edge that will connect these $k$ components. I doubt this gives the optimal solution in all cases but it might be a reasonable heuristic?
– D.W.
Oct 21 at 22:14

For a set of items $$I$$ and the number of bins $$k$$, create a complete bipartite graph of size $$k + |I|$$. Each left vertex corresponds to a bin and has weight $$0$$ (or an appropriately small number if strictly-positive weight is required). Each right vertex corresponds to an item and has the item's weight. Finally, a root vertex is added and connected to all $$k$$ left vertices.
A proper subtree of a spanning tree of the constructed graph corresponds to a set of items packed in a bin. The subtree weight corresponds to the total item weight. A bin packing solution with bin capacity $$C$$ corresponds to a spanning tree with maximum subtree weight $$C$$.
• Thank you. To fill out your argument, for any bin packing with capacity $C$, there's a spanning tree that directly reprsents it and has max subtree weight $C$; for any spanning tree with max subtree weight at most $C$, we can convert it to one where every edge from $\bar{v}$ to the left vertices is taken and that has equal or lesser max subtree weight, i.e. a bin packing with capacity $C$. Oct 23 at 14:42
• So the problem is in $NP$? Oct 23 at 14:43
• "To fill out your argument ..." correct. "we can convert it to one where every edge from v¯ to the left vertices is taken" Or if the number of edges from the root to left vertices is $k' < k$ then it is a bin packing with $k'$ bins. "So the problem is in NP?" The problem is in NP because a spanning tree is a certificate of a solution. Oct 24 at 4:00