# knapsack with graph connectivity constraints

I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally:

• The input is an undirected graph $$G=(V,E)$$, where each node $$v\in V$$ has both a size and a value; and a knapsack capacity $$C$$.
• The goal is to find a subset $$U\subseteq V$$ such that the sum of sizes of all nodes in $$U$$ is at most the capacity $$C$$, and in addition, there is a path between every two nodes in $$U$$; subject to this, the sum of values of all nodes in $$U$$ should be as large as possible.

The original problem is NP-hard, but has a pseudopolynomial-time algorithm. The problem with the additional constraint is definitely NP-hard too; does it have a pseudopolynomial-time algorithm?

There shouldn't be a pseudopolynomial-time algorithm; the problem is NP-hard even if all values are given in unary. We can reduce from the $$\textsf{Connected Vertex Cover}$$ problem in which we need to decide whether a graph has a connected subgraph of at most $$k$$ vertices touching all edges. This is NP-hard by a simple reduction from standard Vertex Cover (simply add an extra vertex and connect it to everything else).
For our reduction, take the input graph $$G = (V, E)$$ of $$\textsf{Connected Vertex Cover}$$ and build $$G'$$ with vertex set $$V \cup E$$ and edge set $$E \cup \{(v, e) \in V \times E \mid v \in e\}$$. Make the size of vertices in $$V$$ equal to $$1$$, and the size of the vertices in $$E$$ equal to $$0$$. Set the value of the vertices in $$E$$ equal to $$1$$, and put value 0 for those in $$V$$. We set the capacity for the knapsack instance equal to $$k$$, the desired connected vertex cover size.
Now for any connected vertex cover $$S$$ of $$G$$ of size at most $$k$$, the subgraph induced by $$S \cup E$$ in $$G'$$ has value $$|E|$$ while respecting the capacity. For the other direction, any connected subgraph $$S'$$ of $$G'$$ of value $$|E|$$ and size at most $$k$$ must include all vertices in $$E$$, while not including more than $$k$$ vertices of $$E$$. That means that $$|S' \cap V| \leq k$$, and also that $$(S' \cap V)$$ is a vertex cover for $$G$$. It only remains to show that $$(S' \cap V)$$ is connected in $$G$$, which is direct, since for any pair of vertices $$u, v \in (S' \cap V)$$, there was a path $$u \to e_1 \to v_1 \to e_2 \to v_2 \to \cdots \to e_\ell \to v$$ in $$G'$$ proving its connectedness, and now $$u \to v_1 \to v_2 \to \cdots \to v$$ is a path in $$G$$.