Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that, 1. Sum of all values in $V^*$ crosses threshold $t$. 2. Sum of all weights(say $w^*$) in $V^*$ is as low as possible. A practical example is finding smallest continuous area of a country that hosts at least $x\%$ of the population. In this case, value would be population, and weight would be area. I found a [related question][1], but it only asks about the complexity, not the algorithm. I thought of 0 - 1 knapsack, such that values and weights swap role. So, 1. Size of knapsack is $t$, however we are allowed to cross it once. 2. minimize $w^*$. However, I think this won't work, mainly because we can't order the nodes by $value/weights$, and secondly because of ability to exceed knapsack size. [1]: https://cs.stackexchange.com/questions/93877/largest-weight-limited-connected-subgraph-np-complete