# Minimum cut on a directed graph with negative term

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?

• 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 Dec 11 '17 at 0:45
• from directed max-cut, you mean – David Eppstein Dec 11 '17 at 6:55
• 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 Dec 18 '17 at 0:41