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)$$

  • 1
    $\begingroup$ The maximum is when $U_2=V_2=\emptyset$. $\endgroup$ – Brendan McKay May 29 '18 at 19:21
  • $\begingroup$ I assume it is nonempty $\endgroup$ – Thomas Edison May 29 '18 at 19:24
  • 3
    $\begingroup$ 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. $\endgroup$ – Brendan McKay May 30 '18 at 8:39

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.