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.
 A: 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{equation}
c(e)=1 \hspace{2mm} \forall \hspace{1mm} e \in A
\end{equation}
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!
