1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.