# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 3 KPCC on Bipartite Graphs
Then, \(\mathbf{x}^{*}\) is said to be \(\epsilon\)-optimal if \(\frac{OB|(\mathbf{x}^{0})}{OB|(\mathbf{x}^{*})}\leq\epsilon\), where \(OBJ(\mathbf{x})\) is the objective function value of the solution \(\mathbf{x}\). When \(\epsilon=1\), then \(\mathbf{x}^{*}\) is an optimal solution. Consider KP1 and KP2, as indicated in Theorem 2. Let \(\mathbf{\dot{x}_{1}}\) and \(\mathbf{\dot{x}_{2}}\) be \(\epsilon\)-optimal solutions to KP1 and KP2, respectively. Define the solutions \(\mathbf{\dot{x}^{1}}\) and \(\mathbf{\dot{x}^{2}}\), where  
\[\mathbf{\dot{x}^{1}}_{j}= \begin{cases}\mathbf{\dot{x}^{1}_{j}}&\text{if }\mathbf{x}\in V_{1}\\ 0&\text{otherwise}\end{cases} \text{ and }\mathbf{\dot{x}^{2}}_{j}= \begin{cases} \mathbf{\dot{x}^{2}_{j}}&\text{if }\mathbf{x}\in V_{2}\\ 0&\text{otherwise}\end{cases} \]  
**Theorem 5**: _The best solution amongst \(\hat{\mathbf{x}}^{1}\) and \(\hat{\mathbf{x}}^{2}\) is a 2e-optimal solution to KPCC on \(G=(V_{1}\cup V_{2},E)\)._  
Let \(\mathbf{x}^{0}\) be an optimal solution to KPCC on \(G=(V_{1}\cup V_{2},E)\). Define the solutions \(\mathbf{x}^{*}\) and \(\mathbf{x}^{**}\) such that  
\[x_{j}^{*}= \begin{cases}x_{j}^{0}&\text{if }\mathbf{a}\in V_{1}\\ 0&\text{otherwise}\end{cases} \text{ and }x_{j}^{**}= \begin{cases}x_{j}^{0}&\text{if } \mathbf{a}\in V_{2}\\ 0&\text{otherwise}\end{cases} \]  
Let \(\mathbf{x}^{1*}\) be the restriction of \(\mathbf{x}^{*}\) to \(V_{1}\) and \(\mathbf{x}^{2**}\) be the restriction of \(\mathbf{x}^{**}\) to \(V_{2}\). Then, \(\mathbf{x}^{1*}\) and \(\mathbf{x}^{2**}\) are feasible solutions of KP1 and KP2, respectively. Then, by the \(\epsilon\)-optimality of \(\hat{\mathbf{x}}_{1}\) and \(\hat{\mathbf{x}}_{2}\) to KP1 and KP2, we have  
\[\sum_{j\in V_{1}}c_{j}\hat{x}_{j}^{1}\leq\epsilon\left(\sum_{j\in V_{1}}c_{j}x _{j}^{1*}\right)=\epsilon\mathbf{c}\mathbf{x}^{*} \tag{1}\]  
and  
\[\sum_{j\in V_{2}}c_{j}\hat{x}_{j}^{2}\leq\epsilon\left(\sum_{j\in V_{2}}c_{j}x _{j}^{2**}\right)=\epsilon\mathbf{c}\mathbf{x}^{**} \tag{2}\]  
Without a loss of generality, assume \(\epsilon\hat{\mathbf{x}}^{1}\geq\epsilon\hat{\mathbf{x}}^{2}\). Then,  
\[\mathbf{c}\mathbf{x}^{0}=\mathbf{c}\mathbf{x}^{*}+\mathbf{c}\mathbf{x}^{**} \leq\epsilon\epsilon\hat{\mathbf{x}}^{1}+\epsilon\epsilon\hat{\mathbf{x}}^{2} \leq 2\epsilon\epsilon\hat{\mathbf{x}}^{1}.\]  
An approximation algorithm \(\mathcal{A}\) for a combinatorial optimization problem (in maximization form) is said to be a \(\delta\)_-fully polynomial time approximation scheme_ (\(\delta\)-FPTASs) if it guarantees a solution \(\mathbf{x}^{*}\) such that \(OBJ(X^{0})\leq\delta(1+\epsilon)OBJ(\mathbf{x}^{*})\), where \(\mathbf{x}^{0}\) is an optimal solution and \(\mathcal{A}\) runs in polynomial time in the input size and \(\frac{1}{\epsilon}\) for any \(\epsilon>0\). Thus, a \(1-FPTASs\) is precisely an \(FPTASs\). Since KP1 and KP2 admits FPTASs, from Theorem 5, KPCC admits \(2-FPTASs\). This result is interesting because the problem is strongly NP-complete on bipartite graphs with maximum vertex degree of three [3; 33]. Further, when KP1 and KP2 are solvable in polynomial time, KPCC on a general bipartite graph can be solved by a polynomial time 2-approximation algorithm. When \(a_{j}=1\) for all \(j\), Theorem 5 reduces to a corresponding result obtained by [PERSON] et al. [2], and for the special case, they showed that the performance bound is asymptotically tight. We summarize these observations in the following corollary. **Corollary 1**: _KPCC on a bipartite graph admits 2-FPTASs. Further, when KP1 and KP2 are solvable in polynomial time, then a 2-optimal solution to KPCC on a bipartite graph can be obtained in polynomial time, and in this case the bound 2 is asymptotically tight._  
The concept of \(\mathcal{F}\)-bipartite graphs can be extended to the more general case of \(\mathcal{F}\)-multipartite graphs. Let \(G=\left(\cup_{k=1}^{p}V_{k},E\right)\) be an undirected graph such that the subgraphs induced by \(V_{k}\) for any \(k=1,2,\ldots,p\) belong to the family \(\mathcal{F}\).