I ran across this problem a while ago, working on identifying edges in dependence cycles for software pipelining. The problem you want to solve is known as the "minimum feedback arc set" problem and is NP-hard. In my case, I could use other knowledge about the problem domain to find a good approximate solution. I'll refer you to the Wikipedia article: http://en.wikipedia.org/wiki/Feedback_arc_set I hope that helps.