2
$\begingroup$

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}$.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Oct 21, 2022 at 22:14

1 Answer 1

Reset to default
3
+50
$\begingroup$

This problem is NP-complete. There exists a reduction from the bin packing problem to this problem.

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$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Andrew
    Oct 23, 2022 at 14:42
  • $\begingroup$ So the problem is in $NP$? $\endgroup$
    – Andrew
    Oct 23, 2022 at 14:43
  • 1
    $\begingroup$ "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. $\endgroup$
    – pcpthm
    Oct 24, 2022 at 4:00
  • $\begingroup$ oh yes of course, whoops $\endgroup$
    – Andrew
    Oct 24, 2022 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.