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?

  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Jun 17 '18 at 20:06
  • $\begingroup$ 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. $\endgroup$ – Thomas Edison Jun 18 '18 at 8:19
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Jun 18 '18 at 15:19

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.