We study the Knapsack problem with graph-theoretic constraints. That is, there exists a graph structure on the input set of items of Knapsack and the solution also needs to satisfy certain graph theoretic properties on top of the Knapsack constraints. In particular, we study Connected Knapsack where the solution must be a connected subset of items which has maximum value and satisfies the size constraint of the knapsack. 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(2^{tw log tw} · poly (n) min{s^2, d^2}) where tw, s, d, n are respectively treewidth of the graph, the size of the knapsack, the target value of the knapsack, and the number of items. We also exhibit a (1 − epsilon) factor approximation algorithm running in time O(2^{tw log tw} · poly (n, 1/epsilon)) for every epsilon > 0. We show similar results for Path Knapsack and Shortest Path Knapsack, where the solution must also induce a path and shortest path, respectively. Our results suggest that Connected Knapsack is computationally the hardest, followed by Path Knapsack and then Shortest Path Knapsack.
Short Bio:
Prof. Palash Dey is an Assistant Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Kharagpur. Before joining IIT Kharagpur, he spent around a year as a visiting post-doctoral fellow at the School of Technology and Computer Science (STCS) at Tata Institute of Fundamental Research (TIFR) Mumbai. Before that, he finished his PhD and Master of Engineering from the Department of Computer Science and Automation in 2017 and 2013, respectively. He received the INSPIRE Faculty Award in 2018 and the ACM India Best Dissertation Award in 2017. He has been a fellow of the West Bengal Academy of Science and Technology, Government of West Bengal, India, since 2022 and an INAE Young Associate since 2023. He is an ACM India Eminent Speaker for 2024-26. His research focuses on Algorithmic Game Theory and Parameterized Algorithms.
