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

Problem Detail: 

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.

Asked By : George

Answered By : Peter Shor

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6476