Is Logical Min-Cut Problem, NP-Complete? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T03:02:20Z http://mathoverflow.net/feeds/question/95239 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95239/is-logical-min-cut-problem-np-complete Is Logical Min-Cut Problem, NP-Complete? valizadeh80 2012-04-26T08:37:37Z 2012-04-27T03:47:54Z <p><b>Logical Min Cut (LMC) Problem:</b> 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 <i>logical minimal</i> removal of some edges of G such that t would be unreachable from s.</p> <p><b>Comments</b><br/> <b>1-</b> 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, <b> by considering just one of the constraints of LMC problem, it will be solvable polynomially.</b> <br/> <b>2-</b> 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. <br/><br/> <b>Question(s):</b><br/> 1) Is LMC problem NP-Complete in an arbitrary digraph G? (main question)<br/> 2) Is LMC problem NP-Complete in an arbitrary DAG G?<br/> 3) Is LMC problem NP-Complete in an arbitrary binary DAG G?<br/></p>