Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
2  
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
1  
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
1  
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
show 1 more comment

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
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
    
@George: it's the same argument that shows the regular Min-Cut LP has integral solutions. There should be a lengthier (and more comprehensible) explanation somewhere online. –  Peter Shor Nov 5 '12 at 23:45
    
Ok I will search for it. Thanks again very much for your help! –  George Nov 6 '12 at 0:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.