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?

  • $\begingroup$ 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) $\endgroup$ – D.W. Feb 20 '17 at 22:38
  • $\begingroup$ @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$). $\endgroup$ – xavierm02 Feb 21 '17 at 10:33
  • $\begingroup$ Take a look at this paper: Node-Optimal Connected k-Subgraphs $\endgroup$ – Willard Zhan Feb 21 '17 at 11:15
  • $\begingroup$ @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? $\endgroup$ – D.W. Feb 21 '17 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.