# Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights

I ran into the following problem:

Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.

For general graphs this is NP-hard, since one can trivially reduce max-cut to it by simply reversing the edge weights (correct me if I'm wrong).

What is the situation with DAGs? Can min-cut (or max-cut) be solved in polynomial time? Is it NP-hard and, if so, are there any known approximation algorithms?

I tried to find work on this but wasn't able to (maybe I'm just using wrong keywords in my searches), so I was hoping somebody may know (or find) something about this.

-
Where does the linear-programming formulation of min-cut fail here? – Peter Shor Nov 5 '12 at 0:20
(using the notation from en.wikipedia.org/wiki/…): For edges with negative weights d_{ij} can be arbitrarily large. Even if one bounds d_{ij} from above, it will always take the maximum possible value for edges with negative weights. So the solution to such a program will not always yield a valid s-t cut. I may be wrong since I'm not very experienced with such problems, if so please correct me. Basically I would like to know whether max-cut (with arbitrary weights) can be solved efficiently for DAGs or not. – George Nov 5 '12 at 12:13
To make this work, you have to change the first inequality to an equality: $d_{ij} = p_j - p_i$. I still don't see why it fails then, but maybe I'm missing something. I haven't thought about it much. – Peter Shor Nov 5 '12 at 12:17
It's probably me who is missing something here. Does this guarantee that all $p_i$ take integral values? One could bound $p_i$ from above with 1, but I'm not sure whether this works or not. The problem seems to be that if this can be solved, one could reduce max-cut to it by reversing the edge weights, which should not be possible since max-cut is NP-hard. However I might be wrong here. – George Nov 5 '12 at 12:40
Is s-t max-cut NP-hard for DAGs? If the graph's not a DAG, you can't change that inequality to an equality, because you need the inequality if there are cycles. So in the general case the LP doesn't work with negative weights. – Peter Shor Nov 5 '12 at 13:14

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_i\geq w$ in the first set of vertices, and all vertices with $p_i < w$ in the second set.
Thanks for your excellent answer Peter. It wasn't obvious at first sight that $0 \leq p_i leq 1$, but I think I got it. However, I have some trouble understanding the argument about the integral solution. – George Nov 5 '12 at 22:01