# Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?

Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint subsets $V_1, V_2 \subseteq V$ such that

$$w(U_1, V_1)+w(U_2, V_2) - w(U_1, V_2) - w(U_2, V_1)$$

is maximal, where

$$w(U_i, V_j):= \sum\limits_{e \in E(U_i,V_j)}w(e)$$

• The maximum is when $U_2=V_2=\emptyset$. – Brendan McKay May 29 '18 at 19:21
• I assume it is nonempty – Thomas Edison May 29 '18 at 19:24
• The maximum for non-empty sets occurs when $U_2$ and $V_2$ contain one vertex each. Just try all the possibilities. Note that the sum of the four $w(*,*)$ quantities is the total weight of all edges, so maximising your objective function is the same as minimising $w(U_1,V_2)+w(U_2,V_1)$. For any $U_1$, the first term achieves its minimum when $V_2$ is a singleton and similarly for the second term. – Brendan McKay May 30 '18 at 8:39