Is Logical Min-Cut Problem, NP-Complete? [closed]

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by the removal of some edges of G but following two constraints: (1) the number of the removed edges must be minimal and (2) we cannot remove every exit edges of any vertex of G. We call logical removal the second constraint. So we look for logical minimal removal of some edges of G such that t would be unreachable from s.

• I took the liberty to add a couple of relevant tags; hope that is ok. Please retag as necessary. Also, it is clear that it is not always possible to make $s$ and $t$ separable --- for example, take a line graph. – Suvrit Apr 27 '12 at 3:48
• 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. – valizadeh80 May 2 '12 at 5:46