Selecting connected subgraph that exceeds value c, with least possible weight

Question

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.

Answer 1

This problem is NP-hard. Let $S = \{x_1, \dots, x_n\}$ be an instance of partition. Create a clique $G$ on $n$ nodes $v_1, \dots, v_n$. Set both the cost and the weight of $v_i$ to $x_i$. Set $t = \frac{1}{2}\sum_{x_i \in S} x_i$.

If there is a subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$, then the set of vertices $\{v_i \mid x_i \in C\}$ is connected, has total value $t$ and total weight $t$.

If there is no subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$ then every subset of vertices of $G$ either has total value smaller than $t$ (and hence is not a feasible solution), or has a total value larger than $t$, and hence also weight larger than $t$.

Then you have that the answer to the instance of partition is yes if and only if the optimal solution to your problem has measure (total weight) $t$.

Answer 2

Here is another reduction from minimum Steiner tree that also shows that your problem is strongly NP-hard.

Let $\langle G, T \rangle$ be an instance of minimum Steiner tree, where $G=(V,E)$ is a graph and $T$ is a set of terminals. Let $w_e$ be the weight of edge $e$ in $G$ and assume that all $w_e$ are positive.

Construct a new graph $G'$ by starting from $G$ and splitting each edge $e$ by adding vertex $v_e$, i.e., replace $e=(u,v)$ with the two edges $(u, v_e)$ and $(v_e, v)$. Assign weight $w_e$ to each $v_e$. Assign value $1$ to all vertices in $T$. All unspecified weights/values are $0$.

An instance of your problem consists of the graph $G'$ and the threshold $t=|T|$.

A Steiner tree $S=(V',E')$ of $G$ having weight at most $W$ can be converted into a subgraph $H$ of $G'$ with weight $W$ and value $t$. Simply chose $H$ as the subgraph of $G'$ induced by the vertices in $V' \cup \{v_e \mid e \in E'\}$.

Similarly, a solution $H=(V',E')$ of weight $W$ to your problem must contain all terminals and can be converted into a Steiner tree $S$ with weight at most $W$ by taking any spanning tree of the subgraph $G_H$ of $G$ induced by the edges in $\{ e \in E \mid v_e \in V'\}$. Notice that if $H$ is an optimal solution to your problem then $G_H$ is already tree (this is ensured by the condition $w_e > 0$).