# Finding the smallest tree of given weight

Take a node-weighted, undirected graph $G$, and a node $r$ in $G$. Is there an efficient algorithm to find a tree in $G$ rooted at $r$ which has total weight at least $w$ and contains a minimal number of nodes?

• Welcome to CS.SE! What have you tried? What approaches have you considered, and why have you rejected them? Have you tried checking whether a greedy algorithm works? (e.g., add the highest-weight edge that connects to the tree, without creating a cycle, or something like that) – D.W. Feb 20 '17 at 22:38
• @D.W. It's node-weighted (and so being a tree isn't a problem, you can just find a connected subgraph and then remove some edges to make it a tree). And the greedy algorithm doesn't work (long path of nodes of weight two starting from the root, and one node of weight $1$ between the root and another node of weight $w$). – xavierm02 Feb 21 '17 at 10:33
• Take a look at this paper: Node-Optimal Connected k-Subgraphs – Willard Zhan Feb 21 '17 at 11:15
• @WillardZhan, want to write that as an answer and summarize the main result of the paper (i.e., the answer to the original question), so we can upvote it? – D.W. Feb 21 '17 at 17:54