**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.

**Comments**

**1-** If we ignore the logical removal constraint of LMC problem, it will be min-cut problem in the unweighted digraph G so it will be solvable polynomially (max-flow min-cut theorem). Furthermore, If we ignore the minimal removal constraint of LMC problem, it will be again solvable polynomially because it is sufficient to find the vertex k such that k is reachable from s and t is not reachable from k. Then consider the path p which is an arbitrary path from s to k. Now consider the path p as a subgraph of G. The answer will be every exit edges of the subgraph p. It is obvious that the vertex k can be found by some DFS in G in polynomial time. Hence, ** by considering just one of the constraints of LMC problem, it will be solvable polynomially.**

**2-** I tried to solve LMC problem by dynamic programming technique but the number of the required states for solving the problem became exponential. Moreover, I tried to reduce some NP-Complete problems such as 3-SAT, max2Sat, max-cut, and clique to LMC problem but I had some problems in reduction.Finally, I personally think that LMC problem is NP-Complete even if G is a binary DAG.

**Question(s):**

1) Is LMC problem NP-Complete in an arbitrary digraph G? (main question)

2) Is LMC problem NP-Complete in an arbitrary DAG G?

3) Is LMC problem NP-Complete in an arbitrary binary DAG G?

tunreachable fromsby the removal of every exit edges of some vertices ofGsuch ass. In min-cut problem, this may happen but in our problem, you're not allowed to do this. As an illustrating example, consider the digraphGwith the verticesv1,v2,v3,v4and the edges(v1,v2),(v2,v3),(v2,v4). If we want to makev4unreachable fromv1, 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)) – valizadeh80 Apr 28 '12 at 7:35tunreachable fromsregarding the constraint#2 (logical removal). By a simple observation, we can see that:LMC problem has answer iff there exists a vertexGenerally, 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. – valizadeh80 Apr 28 '12 at 7:35ksuch thatkis reachable fromsandtis not reachable fromkwhich is determinable polynomially by some DFS.