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.

  • $\begingroup$ 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$? $\endgroup$ – Chao Xu Sep 14 '14 at 23:11
  • $\begingroup$ @ChaoXu apparently the values only. $\endgroup$ – Yixin Cao Sep 15 '14 at 1:05
  • $\begingroup$ I would like the actual cuts, but values would be interesting too. $\endgroup$ – jkff Sep 15 '14 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.