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

<p>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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2014-09-14T23:11:24.477Z
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
CC BY-SA 3.0
2014-09-15T01:05:45.567Z
@ChaoXu apparently the values only.
Yixin Cao
CC BY-SA 3.0
2014-09-15T02:01:13.773Z
I would like the actual cuts, but values would be interesting too.
jkff
<graph-theory><graph-algorithms><directed-acyclic-graph><max-flow-min-cut>
Indexing structure for all-pairs min-cuts in a huge DAG
jkff
# Indexing structure for all-pairs min-cuts in a huge DAG

(Asked by: username_0 on 2014-09-14)

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.

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph, max-flow-min-cut
> **Comments:**
> **username_1**: 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$?  
> **username_2**: @ChaoXu apparently the values only.  
> **username_0**: I would like the actual cuts, but values would be interesting too.  

---

## 0 answers

