1
$\begingroup$

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

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

0

Reset to default

You must log in to answer this question.