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 } & sum_{(i,j) in E} c_{ij} d_{ij} mathrm{subject to } & d_{ij} = p_i – p_j forall (i,j) in E & d_{ij} geq 0 , forall (i,j) in E & p_s, = 1 & p_t , = 0 end{align*} $$ These equations guarantee that $0 leq p_i leq 1$, since every vertex is on some $s$–$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_igeq w$ in the first set of vertices, and all vertices with $p_i < w$ in the second set.