# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 3 KPCC on Bipartite Graphs  
Let \(G=(V_{1}\cup V_{2},E)\) be a bipartite graph with the generic bipartition of its vertex set as \(V_{1}\cup V_{2}\), where \(V_{1}=\{1,2,\ldots,m\}\) and \(V_{2}=\{m+1,m+2,\ldots,m+n\}\). Note that KPCC is trivial to solve when \(G\) is a complete graph and is the same as the knapsack problem when \(G\) is a collection of isolated nodes. When \(G\) is a tree, [PERSON] and [PERSON] [31] showed that KPCC is NP-hard but solvable in \(O(nb^{2})\) time and \(O(nb)\) space. Further, they showed that the algorithm can be modified to obtain a fully polynomial approximation scheme (FPTASs) for KPCC. Trees, in some sense, can be viewed as an extreme case of sparse connected bipartite graphs. Let us now look at KPCC on the complete bipartite graph \(K_{m,n}=(V_{1}\cup V_{2},E)\). Although KPCC is trivial on a complete graph, this simplicity does not extend to \(K_{m,n}\). **Theorem 2**. : _KPCC is NP-hard even if the conflict graph is a star (i.e., \(K_{1,n}\)). Further, on a complete bipartite graph, KPCC can be solved in pseudopolynomial time and it admits FPTASs._  
Proof. : It is not difficult to reduce the knapsack problem to a KPCC on \(K_{1,n}\) and this establishes the first part of the theorem. To prove the second part, note that for any solution \(\mathbf{x}\) of a KPCC on \(K_{m,n}\), if \(x_{i}=1\) for any \(i\in V_{1}\) then by the conflict pair constraints, \(x_{i}=0\) for all \(i\in V_{2}\) and vice versa. Thus, KPCC on \(K_{m,n}\) reduces to two knapsack problems  
\[\text{KP1: Maximize} \sum_{j\in V_{1}}c_{j}x_{j}\] \[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\] \[x_{j}\in\{0,1\}\text{ for all }j\in V_{1}\]  
and  
\[\text{KP2: Maximize} \sum_{j\in V_{2}}c_{j}x_{j}\] \[\text{Subject to:} \sum_{j\in V_{2}}a_{j}x_{j}\leq b\] \[x_{j}\in\{0,1\}\text{ for all }j\in V_{2}\]  
The best solution amongst the solutions of KP1 and KP2 solves KPCC on \(K_{m,n}\). Since the knapsack problem can be solved in pseudopolynomial time and it admits FPTASs, the second part of the theorem follows. From the above theorem, if KP1 and KP2 are solvable in polynomial time, then the corresponding KPCC on \(K_{m,n}\) is also solvable in polynomial time. If \(a_{j}=1\) for all \(j\in V_{1}\cup V_{2}\), then obviously KP1 and KP2 are solvable in polynomial time; hence, the corresponding KPCC on \(K_{m,n}\) is also solvable in polynomial time. This is interesting since KPCC on a general bipartite graph is NP-hard even if \(a_{j}=1\) for all \(j\)[31]. [PERSON] and [PERSON] [40] showed that the cross-ratio-ordered bounded knapsack problem on \(n\) variables can be solved in \(O(n)\) time. This, together with Theorem 2, leads to the following theorem. **Theorem 3**. : _If the costs \(c_{i}\) and weight \(a_{i}\) for \(i\in V_{1}\cup V_{2}\) satisfy \(\frac{a_{i+1}}{a_{i}}\leq\left\lfloor\frac{c_{i+1}}{c_{i}}\right\rfloor\) for \(i=1,2,\ldots\)\(m-1\) and \(\frac{a_{i+1}}{a_{i}}\leq\left\lfloor\frac{c_{i+1}}{c_{i}}\right\rfloor\) for \(i=m+1,m+2,\ldots m+n-1\), then KPCC on \(K_{m,n}\) can be solved in polynomial time._We can also mix conditions for different solvable cases for KP1 and KP2 to obtain solvable instances of KPCC on \(K_{m,n}\). For example, if \(a_{i}=\alpha\) for all \(i\in V_{1}\) and \(\frac{a_{i+1}}{a_{i}}\leq\left\lfloor\frac{c_{i+1}}{c_{i}}\right\rfloor\) for \(i=m+1,m+2,\ldots m+n-1\), then KPCC on \(K_{m,n}\) can also be solved in polynomial time. Later, we present additional conditions for polynomially solvable special cases of the knapsack problem that can be used in different combinations for KP1 and KP2 to produce polynomially solvable cases of KPCC on \(K_{m,n}\). Let \(G=(V_{1}\cup V_{2},E)\) be an undirected graph such that the subgraphs induced by \(V_{1}\) and \(V_{2}\) belong to a family \(\mathcal{F}\) of graphs with specific properties. We call such graphs \(\mathcal{F}\)-bipartite (see Figure 1 for an example). If an \(\mathcal{F}\)-bipartite graph contain all edges \((i,j)\) for \(i\in V_{1},j\in V_{2}\), then it is called a complete \(\mathcal{F}\)-bipartite graph.