I'm looking for information about minimal directed cuts (dicuts) in (connected) DAGs (directed acyclic graphs).


A dicut in a directed graph, is a cut $(P\_1,P\_2)$ in which all edges in $E(P\_1,P\_2)$ are in the same direction between the parts of the cut. Minimal is in relation to inclusion of the edge set $E(P\_1,P\_2)$.


Help in any of these directions would be appreciated.


* Although the number of minimal dicuts can be exponential to the order of the graph (see Brendan's answer below) is it possible to generate them in runtime of the actual number of the cuts?
* Given a DAG, could counting the number of its minimal cuts or upper bound be found in sub-exponential time? (is counting the same as generation in this case, complexity wise?)
* Find a random dicut in a DAG? (uniformly random)


The motivation is to find "matching" minimal dicuts in two DAGs, where "matching" is in size (number of edges in the cut) to construct new DAGs by connecting parts from different graphs (maintaining connectivity).


Thank you!



Directed Minimal Cuts in a DAG
Take two full binary trees, one directed towards the root and one away from the root. Identify the leaves of the two trees, so that the two roots become the source and sink of a DAG. If the number of vertices altogether is $n$, the number of minimal cuts is more than $2^{n/3}$. So you can't generate them all in polynomial time. You can find one of them fast using a flow algorithm.


ADDED: [This paper](http://link.springer.com/chapter/10.1007/3-540-55719-9_88) and its sources should provide useful hints.


