Minimum cut on a directed graph with negative term

885 Views Asked by At

Let $G$ be a digraph and $c:E(G)\rightarrow R$. We look for a set $X\subset V(G)$ with $s\in X$ and $t\notin X$ such that $\sum\limits_{e\in \delta^+(X)}c(e)-\sum\limits_{e\in \delta^-(X)}c(e)$ is minimum. Here, $c$ can be any real number(not only positive value). Can we transform this problem into the well-known Minimum Capacity cut problem?

2

There are 2 best solutions below

0
On

If an edge weight is negative, simply reverse the edges direction and make the weight positive. Do this to make all the edge weights positive so that you have the standard min cut problem.

0
On

Your question is a special case of this question which mentions a solution for the special case.