Knapsack: Connectedness, Path, and Shortest-Path
This addresses computational complexity and algorithm design for knapsack variants with graph constraints, which is incremental as it extends classical knapsack problems.
The paper tackles the knapsack problem with graph constraints, showing that connected knapsack is strongly NP-complete for graphs of max degree four and NP-complete for star graphs, and provides an exact algorithm with runtime O(2^{tw log tw}·poly(min{s^2, d^2})) and a (1-ε)-approximation algorithm with runtime O(2^{tw log tw}·poly(n, 1/ε)).
We study the knapsack problem with graph theoretic constraints. That is, we assume that there exists a graph structure on the set of items of knapsack and the solution also needs to satisfy certain graph theoretic properties on top of knapsack constraints. In particular, we need to compute in the connected knapsack problem a connected subset of items which has maximum value subject to the size of knapsack constraint. We show that this problem is strongly NP-complete even for graphs of maximum degree four and NP-complete even for star graphs. On the other hand, we develop an algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(\min\{s^2,d^2\})\right)$ where $tw,s,d$ are respectively treewidth of the graph, size, and target value of the knapsack. We further exhibit a $(1-ε)$ factor approximation algorithm running in time $O\left(2^{tw\log tw}\cdot\text{poly}(n,1/ε)\right)$ for every $ε>0$. We show similar results for several other graph theoretic properties, namely path and shortest-path under the problem names path-knapsack and shortestpath-knapsack. Our results seems to indicate that connected-knapsack is computationally hardest followed by path-knapsack and shortestpath-knapsack.