The Maximum Edge-Weighted Clique Problem in Complete Multipartite Graphs

Abstract

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=(\genfrac{}{}{0ex}{}{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.