Minimum cut set for directed s-t cut

I am given a directed graph $G=(V,E)$, with vertices $s,t\in V$. I need to find an s-t cut with the minimum number of edges crossing it from s towards t, i.e. for every cut $S\subseteq V$ such that $s\in S, t\notin S$, the number of crossing edges is defined as $N(S)=|\<(u\rightarrow v)\in E : u\in S, v\notin S\>|$. The desired cut is one for which $N(S)$ is minimal. Any ideas? Thanks.

1 Answer 1

The way that I would approach this problem is by trying to use the theory behind networks and flows, in particular the Max-Flow Min-Cut theorem.

Consider the network $N=(V,A)$ which is constructed by letting V be the same as in $G$, and by letting $A$ be the set of directed edges from $E$ except with the additional requirement that \begin c(e)=1 \hspace \forall \hspace e \in A \end

Now, when we take a cut $(S, V-S)$, we will have $cap(S,V-S)$ being equal to the number of edges that have tails in $S$ and heads in $V-S$. At this point, the Max-Flow Min-Cut theorem guarantees that we will be able to find a cut where the value of the flow is equal to the capacity of the cut, and importantly that this cut is a minimum cut, meaning the number of arcs coming out of $S$ to $V-S$ is a minimum also.

In terms of actually computing this, one useful algorithm for solving the Max-Flow Min-Cut problem is the Ford-Fulkerson Max Flow Labeling Algorithm (explained in detail here) which basically iterates finding augmenting paths and augmenting the graph until a guaranteed maximum flow is found. Hope that helps!