# Indexing structure for all-pairs min-cuts in a huge DAG

I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution.

Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive dependency between package A and package B, and do other related queries/algorithms.

The question "how to break a transitive dependency" is answered by a min-cut.

Is there a practical indexing structure for answering all-pairs min-cut that works for large DAGs (non-ridiculous time and space complexity)? I am aware of Gomory-Hu trees (though I have not yet grasped them), but they seem to work only for undirected graphs.

• Do you only care about the $s-t$-min cut value or do you also want to have a min-cut for each $s-t$? – Chao Xu Sep 14 '14 at 23:11
• @ChaoXu apparently the values only. – Yixin Cao Sep 15 '14 at 1:05
• I would like the actual cuts, but values would be interesting too. – jkff Sep 15 '14 at 2:01