Knapsack on Graphs with Relaxed Neighborhood Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909591760011264 |
|---|---|
| author | Dey, Palash Hota, Ashlesha Kolay, Sudeshna |
| author_facet | Dey, Palash Hota, Ashlesha Kolay, Sudeshna |
| contents | In the knapsack problems with neighborhood constraints that were studied before, the input is a graph $\mathcal{G}$ on a set $\mathcal{V}$ of items, each item $v \in \mathcal{V}$ has a weight $w_v$ and profit $p_v$, the size $s$ of the knapsack, and the demand $d$. The goal is to compute if there exists a feasible solution whose total weight is at most $s$ and total profit is at most $d$. Here, feasible solutions are all subsets $\mathcal{S}$ of the items such that, for every item in $\mathcal{S}$, at least one of its neighbors in $\mathcal{G}$ is also in $\mathcal{S}$ for \hor, and all its neighbors in $\mathcal{G}$ are also in $\mathcal{S}$ for \hand~\cite{borradaile2012knapsack}. We study a relaxation of the above problems. Specifically, we allow all possible subsets of items to be feasible solutions. However, only those items for which we pick at least one or all of its neighbor (out-neighbor for directed graph) contribute to profit whereas every item picked contribute to the weight; we call the corresponding problems \sor and \sand. We show that both \sor and \sand are strongly \NPC even on undirected graphs. Regarding parameterized complexity, we show both \sor and \hor are \WTH parameterized by the size $s$ of the knapsack size. Interestingly, both \sand and \hand are \WOH parameterized by knapsack size, $s$ plus profit demand, $d$ and also parameterized by solution size, $b$. For \sor and \hor, we present a randomized color-coding-based pseudo-\FPT algorithm, parameterized by the solution size $b$, and consequently by the demand $d$. We then consider the treewidth of the input graph as our parameter and design pseudo fixed-parameter tractable (\FPT) algorithm parameterized by treewidth, $\text{tw}$ for all variants. Finally, we present an additive $1$ approximation for \sor when both the weight and profit of every vertex is $1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17297 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Knapsack on Graphs with Relaxed Neighborhood Constraints Dey, Palash Hota, Ashlesha Kolay, Sudeshna Data Structures and Algorithms Computational Complexity In the knapsack problems with neighborhood constraints that were studied before, the input is a graph $\mathcal{G}$ on a set $\mathcal{V}$ of items, each item $v \in \mathcal{V}$ has a weight $w_v$ and profit $p_v$, the size $s$ of the knapsack, and the demand $d$. The goal is to compute if there exists a feasible solution whose total weight is at most $s$ and total profit is at most $d$. Here, feasible solutions are all subsets $\mathcal{S}$ of the items such that, for every item in $\mathcal{S}$, at least one of its neighbors in $\mathcal{G}$ is also in $\mathcal{S}$ for \hor, and all its neighbors in $\mathcal{G}$ are also in $\mathcal{S}$ for \hand~\cite{borradaile2012knapsack}. We study a relaxation of the above problems. Specifically, we allow all possible subsets of items to be feasible solutions. However, only those items for which we pick at least one or all of its neighbor (out-neighbor for directed graph) contribute to profit whereas every item picked contribute to the weight; we call the corresponding problems \sor and \sand. We show that both \sor and \sand are strongly \NPC even on undirected graphs. Regarding parameterized complexity, we show both \sor and \hor are \WTH parameterized by the size $s$ of the knapsack size. Interestingly, both \sand and \hand are \WOH parameterized by knapsack size, $s$ plus profit demand, $d$ and also parameterized by solution size, $b$. For \sor and \hor, we present a randomized color-coding-based pseudo-\FPT algorithm, parameterized by the solution size $b$, and consequently by the demand $d$. We then consider the treewidth of the input graph as our parameter and design pseudo fixed-parameter tractable (\FPT) algorithm parameterized by treewidth, $\text{tw}$ for all variants. Finally, we present an additive $1$ approximation for \sor when both the weight and profit of every vertex is $1$. |
| title | Knapsack on Graphs with Relaxed Neighborhood Constraints |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2504.17297 |