Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights
You've refined your problem some more in the comments. To be more specific, you have a DAG with all edges flowing away from the source $s$ and towards the sink $t$ (that is, all edges are on a path from $s$ to $t$). You want to find the minimum cut between two pieces of the DAG, where the first piece is connected to $s$, and the second connected to $t$. For this problem, a variation of the standard linear-programming algorithm for MIN-CUT works, even with negative edge weights. 

We use the same notation as in Wikipedia. The cost of edge $(i,j)$ is $c_{ij}$. We put a potential function $p_i$ on each node, and let $d_{ij} = p_i - p_j$. The LP is
$$ \begin{align*} \mathrm{minimize\ } &amp; \sum_{(i,j) \in E} c_{ij} d_{ij} \\
\mathrm{subject\ to\ } &amp; \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &amp;\ \ \ d_{ij}  \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ &amp; \ \ \  p_s\, = 1 \\ &amp; \ \ \ p_t \, = 0  \end{align*} $$ 

These equations guarantee that $0 \leq p_i \leq 1$, since every vertex is on some $s$&ndash;$t$ path. Similarly, since $d_{ij} = p_i - p_j$ is non-negative, the potentials on any path from $s$ to $t$ are decreasing. We still need to show that there is an optimal solution to the LP with all $p_i$ either $0$ or $1$. This follows from the fact that the value to a solution of the LP above is the expected value of the cut $C_w$, where $w$ is chosen randomly in $[0,1]$, and where cut $C_w$ is obtained by putting all vertices $i$ with $p_i\geq w$ in the first set of vertices, and all vertices  with $p_i &lt; w$ in the second set.