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 high 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 inverse of area.

I found a related question, 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. Maximize $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.

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