User valizadeh80 - MathOverflow

Is Logical Min-Cut Problem, NP-Complete?

2012-04-26T08:37:37Z

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?

Comment by valizadeh80

2012-05-02T05:46:24Z

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.

Comment by valizadeh80

2012-04-28T07:35:34Z

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.

Comment by valizadeh80

2012-04-28T07:35:15Z

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))