Menu
The problem we consider is: Given a complete multipartite graph \(G\) with integral weights on the edges, and given an integer \(m\), find a clique \(C\) in \(G\) such that the weight-sum of the edges of \(C\) is greater than or equal to \(m\). We prove that where \(G\) has \(k\) parts, each with at most two nodes, the edge-weights are \(0-1\), and \(m = \binom{k}{2}\), this problem is equivalent to \(2\)-conjunctive normal form satisfiability, and hence is polynomially solvable. However, if either each part has at most three nodes or \(m\) is arbitrary, the problem is NP-complete. We also show that a related problem which is equivalent to a \(0-1\) weighted version of \(2\)-CNF satisfiability is NP-complete.
The maximum edge-weighted clique problem in complete multipartite graphs arises in transit scheduling, where it is called the schedule synchronization problem.