Dear Todd, the received answer is not correct. I finally managed to prove that this problem is NP-Complete.

I am also looking for a good estimation algorithm to solve the LMC problem. As it was told in the comment section of the problem definition, we can solve the problem by finding a path $p$ from $s$ to the vertex $k$ s.t. $k$ is reachable from $s$ and $t$ is not reachable from $k$. So the outgoing edges of the path $p$ (consider $p$ as a subgraph of $G$) will be an answer of the problem because the removal of the outgoing edges of p will make t unreachable from s and it is logical. This solution uses more edges. The answer of a good estimation algorithm should contain as less edges as possible.

In special cases, it is not possible to make t unreachable from s regarding the constraint#2 (logical removal). By a simple observation, we can see that: LMC problem has answer iff there exists a vertex k such that k is reachable from s and t is not reachable from k which is determinable polynomially by some DFS. Generally, ignore such special cases and consider general case of the problem. Moreover, I didn't have permission to define new tags such as 'min-cut' , 'edge-removal', 'logical', etc. Thanks for adding the tags.

Let me clarify the constraint#2 of the LMC problem. If we ignore the constraint#2, it will be possible to make t unreachable from s by the removal of every exit edges of some vertices of G such as s. In min-cut problem, this may happen but in our problem, you're not allowed to do this. As an illustrating example, consider the digraph G with the vertices v1,v2,v3,v4 and the edges (v1,v2),(v2,v3),(v2,v4). If we want to make v4 unreachable from v1, you cannot remove the edge (v1,v2) but you can remove the edge (v2,v4) because the edge (v2,v4) has a sibling edge ((v2,v3))