Skip to main content

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct. Is it?

Given a bipartite graph $G = (U,V, E)$$G = (U, V, E)$ with weights $w: E\to \mathbb{R}_+$. Find$w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and a 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 maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$

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

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct.

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 a 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 maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$

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

Partition Is the partition of bipartite graph isgraphs NP-hard?

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct.

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 a 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)$$$w(U_1, V_1)+w(U_2, V_2) - w(U_1, V_2) - w(U_2, V_1)$$ is maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$

Partition of bipartite graph is NP-hard?

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct.

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 a 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 maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$

Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct.

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 a 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 maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$

Source Link

Partition of bipartite graph is NP-hard?

I wonder if the following problem is NP-hard but I have no idea whether or not it is correct.

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 a 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 maximum, where $$w(U_i,V_i):= \sum\limits_{e\in E(U_i,V_i)}w(e).$$