3
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Please define "minimal" more precisely. Usually a "cut" means a partition of the vertex set into two parts, but I think you might be referring to inclusion of the edge sets between the parts rather than inclusion (defined somehow) of the two vertex sets. $\endgroup$
    – Brendan McKay
    Commented Oct 5, 2014 at 0:46
  • $\begingroup$ To motivate my question: Consider two vertices $s,t$ with $n-2$ directed paths of two edges between them. Each of the $2^{n-2}$ choices of one edge from each path is an edge-cutset which is minimal in one sense not in the other. By expanding $s,t$ into suitable digraphs you can make the total degree of each vertex at most 3 and still have exponentially many cuts. $\endgroup$
    – Brendan McKay
    Commented Oct 5, 2014 at 3:43
  • $\begingroup$ Hi @BrendanMcKay, thanks for the comment. I was not precise enough. A directed cut is defined (here) as a cut (partition of the vertex set) $(P_1,P_2)$ in which all the edges between the parts, $E(P_1,P_2)$ are in the same direction, say from $P_1$ to $P_2$. (the "directed" subset of the co-cycle space). Minimality in in relation to inclusion of the edge set $E(P_1, P_2)$ (minimal directed elements in the co-cycle space ordered by inclusion). $\endgroup$
    – Daugmented
    Commented Oct 5, 2014 at 11:58

1 Answer 1

Reset to default
4
$\begingroup$

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 and its sources should provide useful hints.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't know how to randomly sample a minimum cut. $\endgroup$
    – Brendan McKay
    Commented Oct 6, 2014 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .