<p>Suppose we are given a directed Graph $G=(V,E)$ and there is a nonnegative weight $w(u,v)$ is defined for the edge from $u$ to $v$. The task is to partition vertices to $A$ and $B$ (partition means $V = A \cup B$ and $A \cap B = \emptyset$) such that the following value is minimized: 
$$\Sigma_{u \in A, v\in B} w(u,v) - \Sigma_{u \in B, v \in A} w(u,v)$$
Here the difference with the classic notion of min-cut is the presence of the negative term. Otherwise, a max-flow algorithm between a pair of vertices would have been the answer. Can this problem also be formulated in a flow framework? </p>

<p>Besides that, is the best way to do max-flow on all possible pair of nodes, or there is a smarter way to do it? </p>

CC BY-SA 3.0
2017-12-11T00:45:07.040Z
If you can minimize then you can also maximize that quantity, since $(A,B)$ is a minimizer then $(B,A)$ is a maximizer. There is likely a reduction to directed max-cut.
Chao Xu
CC BY-SA 3.0
2017-12-11T06:55:07.320Z
_from_ directed max-cut, you mean
David Eppstein
CC BY-SA 3.0
2017-12-18T00:41:21.787Z
About the last question: you can pick one node arbitrary and run max-flow only on pairs $(v_0,v)$ where $v_0$ is the picked node and $v \in V$.
Artur Riazanov
<graph-theory><max-flow-min-cut>
Minimum cut on a directed graph with negative term
AmeerJ
# Minimum cut on a directed graph with negative term

(Asked by: username_0 on 2017-12-10)

Suppose we are given a directed Graph $G=(V,E)$ and there is a nonnegative weight $w(u,v)$ is defined for the edge from $u$ to $v$. The task is to partition vertices to $A$ and $B$ (partition means $V = A \cup B$ and $A \cap B = \emptyset$) such that the following value is minimized:
$$\Sigma\_{u \in A, v\in B} w(u,v) - \Sigma\_{u \in B, v \in A} w(u,v)$$
Here the difference with the classic notion of min-cut is the presence of the negative term. Otherwise, a max-flow algorithm between a pair of vertices would have been the answer. Can this problem also be formulated in a flow framework?

Besides that, is the best way to do max-flow on all possible pair of nodes, or there is a smarter way to do it?

**Tags:** graph-theory, max-flow-min-cut

> **Comments:**
> **username_1**: If you can minimize then you can also maximize that quantity, since $(A,B)$ is a minimizer then $(B,A)$ is a maximizer. There is likely a reduction to directed max-cut.  
> **username_2**: _from_ directed max-cut, you mean  
> **username_3**: About the last question: you can pick one node arbitrary and run max-flow only on pairs $(v_0,v)$ where $v_0$ is the picked node and $v \in V$.  

---

## 0 answers

