# The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions
## 2 Literature Review
In another paper, [PERSON] and [PERSON] [32] investigated approximation algorithms for KPCC under various restrictions on \(G\). They showed that KPCC admits FPTASs on weakly chordal graphs and is solvable by PTAS (not FPTASs) on planar graphs. [PERSON] et al. [2] studied another special case of KPCC, where \(a_{j}=1\) for all \(j=1,2,\ldots,n\) and \(G\) is a multipartite graph. They proposed a \(\frac{1}{k}\)-approximation algorithm, where \(k\) is the number of partite sets, and proved that the performance bound established is tight. If \(a_{j}=1\) and \(c_{j}\) equal to the degree of \(j\), for \(j=1,2,\ldots,n\), KPCC reduces to the maximum independent vertex coverage problem (MIVC). The authors proved approximation hardness results for MIVC and showed that MIVC is NP-hard on bipartite graphs. Further, they established bounds on the integrality for the LP relaxation of a clique-based formulation of MVIP. [PERSON] [1] investigated another special case of KPCC, where \(c_{j}=1\) for all \(j\). This problem is called the maximum budget independent set problem (MBIS), and the author presented a factor \(d\) polynomial time approximation algorithm for the problem on \((d+1)\)-claw free graphs. In KPCC, if we restrict the budget constraint to be satisfied as an equality, we obtain an instance of the _exact knapsack problem with conflict pair constraints_ (KPCC-exact). The feasibility version of this problem was investigated by [PERSON] and [PERSON] [3; 33], where it was shown that the problem is strongly NP-complete on bipartite graphs with maximum vertex degree of three. The authors also presented a pseudo-polynomial algorithm for the problem in cographs, chordal graphs, and interval graphs. A generalization of KPCC involving more than one knapsack constraint was studied by [PERSON] [34], where a Dantzig-Wolfe decomposition scheme was proposed. [PERSON] et al. [35] used conflict graphs in developing algorithms for 0-linteger programs. The _quadratic knapsack problem_ (QKP) [36] can be stated as  
\[\text{Maximize} \quad\mathbf{x}^{t}Q\mathbf{x}+\mathbf{c}\mathbf{x}\] \[\text{Subject to:} \mathbf{a}\mathbf{x}\leq b\] \[\mathbf{x}\in\{0,1\}^{n}\]  
where \(Q=(q_{ij})\) is an \(n\times n\) matrix. Although the QKP appears to be more general than KPCC, we now observe that QKP and KPCC are essentially equivalent, in the sense that one is a special case of the other. Theorem 1: _QKP and KPCC are equivalent._  
Proof. : Define the matrix \(Q=(q_{ij})\) such that \(q_{ij}=-M\), where \(M\) is a large positive number if \((i,j)\in E\) and \(q_{ij}=0\) otherwise. With this choice of \(Q\), the problem KPCC reduces to QKP. Thus, KPCC is a special case of QKP. Let us now prove the converse. That is, QKP is a special case of KPCC. This is, however, achieved by appropriate modifications in the well-known reduction of a quadratic unconstrained binary optimization problem (QUBO) to the maximum weight stable set problem [37; 38] to handle the budget constraint. Thus, KPCC can be viewed as a generalization of QKP. For further details on QUBO, refer to [39]. The major contributions of the paper can be summarized as follows. * We present new complexity results on KPCC along with a thorough state-of-the-art review of the literature. Also, we show that KPCC and QKP are equivalent. * When the conflict graph is a complete bipartite graph, it is shown that KPCC decomposes into two knapsack problems. As a consequence, we have new polynomially solvable (and pseudo-polynomially solvable) special cases of KPCC and have special cases of KPCC that admit FPTASs. These results are extended to more general classes of graphs that accept a blakbox oracle with special properties. On a star (which is a special bipartite graph), the problem is shown to be NP-hard. * A new integer programming formulation that unifies and generalizes existing formulations of KPCC on general graphs is given. The strengths of the LP relaxation of this formulation and of special cases are analyzed theoretically.