Abstract
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 \(\textsf{NP}\)-complete even for graphs of maximum degree four and \(\textsf{NP}\)-complete even for star graphs. On the other hand, we develop an algorithm running in time \(\mathcal O \left( 2^{\mathcal O (\text {tw} \log \text {tw})}\cdot \text {poly}(n)\min \{s^2,d^2\}\right) \) where \(\text {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-\varepsilon )\) factor approximation algorithm running in time \(\mathcal O \left( 2^{\mathcal O (\text {tw} \log \text {tw})}\cdot \text {poly}(n,1/\varepsilon )\right) \) for every \(\varepsilon >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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
A faster parameterized algorithm for pseudoforest deletion. Discrete Applied Mathematics 236, 42–56 (2018)
Bettinelli, A., Cacchiani, V., Malaguti, E.: A branch-and-bound algorithm for the knapsack problem with conflict graph. INFORMS J. Comput. 29(3), 457–473 (2017). https://doi.org/10.1287/ijoc.2016.0742
Bonomo, F., de Estrada, D.: On the thinness and proper thinness of a graph. Discret. Appl. Math. 261, 78–92 (2019). https://doi.org/10.1016/J.DAM.2018.03.072
Bonomo-Braberman, F., Gonzalez, C.L.: A new approach on locally checkable problems. Discret. Appl. Math. 314, 53–80 (2022). https://doi.org/10.1016/J.DAM.2022.01.019
Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems - an overview of recent advances. part I: single knapsack problems. Comput. Oper. Res. 143, 105692 (2022). https://doi.org/10.1016/j.cor.2021.105692,
Cacchiani, V., Iori, M., Locatelli, A., Martello, S.: Knapsack problems - an overview of recent advances. part II: multiple, multidimensional, and quadratic knapsack problems. Comput. Oper. Res. 143, 105693 (2022). https://doi.org/10.1016/j.cor.2021.105693
Coniglio, S., Furini, F., Segundo, P.S.: A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. Eur. J. Oper. Res. 289(2), 435–455 (2021). https://doi.org/10.1016/j.ejor.2020.07.023
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd Edition. MIT Press (2009). http://mitpress.mit.edu/books/introduction-algorithms
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Dey, P., Kolay, S., Singh, S.: Knapsack: Connectedness, path, and shortest-path. CoRR abs/2307.12547 (2023)
Fleischner, H., Sabidussi, G., Sarvanov, V.I.: Maximum independent sets in 3- and 4-regular hamiltonian graphs. Discret. Math. 310(20), 2742–2749 (2010). https://doi.org/10.1016/j.disc.2010.05.028
Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified np-complete problems. In: Constable, R.L., Ritchie, R.W., Carlyle, J.W., Harrison, M.A. (eds.) Proc. 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA, pp. 47–63. ACM (1974). https://doi.org/10.1145/800119.803884
Goebbels, S., Gurski, F., Komander, D.: The knapsack problem with special neighbor constraints. Math. Methods Oper. Res. 95(1), 1–34 (2022). https://doi.org/10.1007/s00186-021-00767-5
Gurski, F., Rehs, C.: Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width. Math. Methods Oper. Res. 89(3), 411–432 (2019). https://doi.org/10.1007/s00186-019-00664-y
Held, S., Cook, W.J., Sewell, E.C.: Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Program. Comput. 4(4), 363–381 (2012). https://doi.org/10.1007/s12532-012-0042-3
Hifi, M., Michrafy, M.: A reactive local search-based algorithm for the disjunctively constrained knapsack problem. J. Oper. Res. Society 57(6), 718–726 (2006)
Hifi, M., Michrafy, M.: Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34(9), 2657–2673 (2007)
Ito, T., Demaine, E.D., Zhou, X., Nishizeki, T.: Approximability of partitioning graphs with supply and demand. J. Discr. Algorithms 6(4), 627–650 (2008)
Kellerer, H., Pferschy, U., Pisinger, D., Kellerer, H., Pferschy, U., Pisinger, D.: Multidimensional knapsack problems. Springer (2004). https://doi.org/10.1007/978-3-540-24777-7_9
Luiz, T.A., Santos, H.G., Uchoa, E.: Cover by disjoint cliques cuts for the knapsack problem with conflicting items. Oper. Res. Lett. 49(6), 844–850 (2021). https://doi.org/10.1016/j.orl.2021.10.001
Mannino, C., Oriolo, G., Ricci-Tersenghi, F., Chandran, L.S.: The stable set problem and the thinness of a graph. Oper. Res. Lett. 35(1), 1–9 (2007). https://doi.org/10.1016/J.ORL.2006.01.009
Martello, S., Toth, P.: Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. (1990)
Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233–249 (2009). https://doi.org/10.7155/jgaa.00186
Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300–1323 (2017). https://doi.org/10.1007/s10878-016-0035-7
Yamada, T., Kataoka, S., Watanabe, K.: Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inform. Process. Society Japan J. 43(9) (2002)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dey, P., Kolay, S., Singh, S. (2024). Knapsack: Connectedness, Path, and Shortest-Path. In: Soto, J.A., Wiese, A. (eds) LATIN 2024: Theoretical Informatics. LATIN 2024. Lecture Notes in Computer Science, vol 14579. Springer, Cham. https://doi.org/10.1007/978-3-031-55601-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-55601-2_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-55600-5
Online ISBN: 978-3-031-55601-2
eBook Packages: Computer ScienceComputer Science (R0)