# Bipartite clustering is NP-hard?

Let $G = (A\cup B, E)$ be a bipartite graph with edge weights $w: E\to \mathbb{R}$. Find a partition $B_1, B_2$ of $B$ and a nonempty disjoint subsets $A_1, A_2$ of $A$ such that $w(A_1,B_1) + w(A_2, B_2)$ is maximum, where $w(A_i, B_i) := \sum\limits_{\{a,b\}\in (A\times B)\cap E}w(a,b)$.

I think this problem is already known but I couldn't find any reference. Does anyone know any related problems? Or is this problem NP-hard?

• Surely to maximize the sum, you should let $A_1$ and $B_1$ be as big as possible; and $A_2$ and$B_2$ as small as possible (ideally empty). The harder problem would be to minimize the sum (or maybe you constrain the size of the $A$’s and $B$’s. Also this is not really a problem about graphs. You could ask the same problem just about matrices with non-negative entries. – Anthony Quas Jun 17 '18 at 20:06
• Thanks for your comment. But I don't think so. The minimization problem is equivalent to the maximization one because the weight $w$ can be positive or negative. – Thomas Edison Jun 18 '18 at 8:19
• If that’s what you have in mind, you should say so explicitly in the question as in this kind of area, weights are generally assumed to be positive. – Anthony Quas Jun 18 '18 at 15:19