0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ – Chao Xu Dec 11 '17 at 0:45
  • 1
    $\begingroup$ from directed max-cut, you mean $\endgroup$ – David Eppstein Dec 11 '17 at 6:55
  • $\begingroup$ 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$. $\endgroup$ – Artur Riazanov Dec 18 '17 at 0:41

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.