# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 3 KPCC on Bipartite Graphs
[PERSON] et al. [41] studied \(\mathcal{F}\)-bipartite graphs, where the induced subgraph of \(V_{1}\) is a collection of isolated nodes and the induced subgraph of \(V_{2}\) is a \(k\)-degenerate graph. Depending on the properties imposed on the family \(\mathcal{F}\), the \(\mathcal{F}\)-bipartite structure can have algorithmic advantages in solving some optimization problems. For example, \(\mathcal{F}\) could contain all classes of graphs on which the KPCC can be solved in pseudo-polynomial time. In this case, \(\mathcal{F}\) includes graphs that are isolated vertices, trees, complete bipartite graphs, complete graphs, chordal graphs, interval graphs, cographs, and circular arc graphs. Assume that for a \(\mathcal{F}\)-bipartite graph, the bipartition \(V_{1}\) and \(V_{2}\) along with the structure of the subgraphs induced by \(V_{1}\) and \(V_{2}\) are given. Then, the results obtained in the previous sections on the solvability of KPCC can be extended to \(\mathcal{F}\)-bipartite graphs. Figure 1: A complete \(\mathcal{F}\)-bipartite graph with \(V_{1}=\{v_{1},v_{2},v_{3},v_{4}\}\) and \(V_{2}=\{u_{1},u_{2},u_{3}\}\). The subgraph induced by \(V_{1}\) is a cycle and a pendant vertex, and the subgraph induced by \(V_{2}\) is tree (path). **Theorem 4**. : _KPCC can be solved in pseudo-polynomial time on a complete \(\mathcal{F}\)-bipartite graph \(G=(V_{1}\cup V_{2},E)\) if KPCC can be solved in pseudo-polynomial time on graphs in \(\mathcal{F}\). Further, KPCC admits FPTASs on \(G\) whenever KPCC admits FPTASs on graphs in \(\mathcal{F}\)._  
Proof. : The proof of the above theorem is similar to that of Theorem 2, except that instead of KP1 and KP2 we will have problems of the type KPCC but with reduced sizes. However, we present the complete proof of the theorem here to facilitate further related discussions. Let \(G_{1}=(V_{1},E_{1})\) be the subgraph of \(G\) induced by \(V_{1}\) and \(G_{2}=(V_{2},E_{2})\) be the subgraph of \(G\) induced by \(V_{2}\). Since every vertex in \(V_{1}\) is connected to every vertex in \(V_{2}\), for any solution \(\mathbf{x}\) of the KPCC, if \(x_{i}=1\) for any \(i\in V_{1}\) then \(x_{i}=0\) for all \(i\in V_{2}\) and vice versa. Thus, KPCC reduces to the following reduced KPCCs. \[\text{KPCC1: 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_{i}+x_{j}\leq 1\text{ for }(i,j)\in E_{1}\] \[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\]0  
and  
\[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\]1 \[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\]2 \[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\]3 \[\text{Subject to:} \sum_{j\in V_{1}}a_{j}x_{j}\leq b\]4  
The best solution amongst the solutions of KPCC1 and KPCC2 provides an optimal solution to KPCC. By assuming the properties of \(\mathcal{F}\), KPCC1 and KPCC2 can be solved in pseudo-polynomial time. The proof of the second part of the theorem also follows in an analogous way. Theorem 4 is a proper generalization of Theorem 2. The results discussed above extend in a natural way to complete multi-partite graphs. However, to take any computational advantage we need to know the partite sets a priori or need to compute them. Bipartite graphs can be recognized in polynomial time but recognizing \(p\)-partite graphs for \(p>2\) is NP-complete [42]. If there are \(p\) partite sets, then we will be solving \(p\) knapsack problems. General Bipartite GraphsWe now consider KPCC on a general bipartite graph \(G=(V_{1}\cup V_{2},E)\), where \(V_{1}=\{1,2,\ldots,m\}\) and \(V_{2}=\{m+1,m+2,\ldots,m+n\}\). Note that we are considering a maximization problem. Consider the maximization version of a combinatorial optimization problem such that the objective function value of its feasible solutions are positive. Let \(\mathbf{x}^{*}\) be any feasible solution to such a problem and \(\mathbf{x}^{0}\) be a corresponding optimal solution.