[Solved]: Is Logical Min-Cut NP-Complete?

Problem Detail: 

Logical Min Cut (LMC) problem definition

Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can make $t$ unreachable from $s$ by the removal of some edges of $G$ following the following constraints:

1. The number of the removed edges must be minimal.
2. We cannot remove every exit edge of any vertex of $G$ (i.e., no vertex with outgoing edges can have all its outgoing edges removed).

This second constraint is called logical removal. So we look for a logical, minimal removal of some edges of $G$ such that $t$ would be unreachable from $s$.

Solution attempts

If we ignore the logical removal constraint of LMC problem, it will be the min-cut problem in the unweighted digraph $G$, so it will be solvable polynomially (max-flow min-cut theorem).

If we ignore the minimal removal constraint of the LMC problem, it will be again solvable polynomially in a DAG: find a vertex $k$ such that $k$ is reachable from $s$ and $t$ is not reachable from $k$. Then consider a 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 edge of the subgraph $p$. It is obvious that the vertex $k$ can be found by DFS in $G$ in polynomial time. Unfortunately this algorithm doesn't work in general for an arbitrary directed graph.

I tried to solve the LMC problem by a dynamic programming technique but the number of 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 the LMC problem I didn't manage to find a reduction.

I personally think that the LMC problem is NP-Complete even if $G$ is a binary DAG (i.e., a DAG where no node has out-degree greater than 2).

Questions

1. Is the LMC problem NP-Complete in an arbitrary digraph $G$? (main question)
2. Is the LMC problem NP-Complete in an arbitrary DAG $G$?
3. Is the LMC problem NP-Complete in an arbitrary binary DAG $G$?

Asked By : amirv

Answered By : amirv

Let G = (V, E) be a weighted DAG, s and t be two vertices of G, and LSTMC = (G, s, t) be an instance of the logical s-t min-cut problem. It is obvious that the LSTMC problem is NP.Now, we should show that the LSTMC is NP-Hard. We reduce the hitting-set problem to the LSTMC problem. Let S = {s1, s2, ..., sn} be the given sets and {a1, a2, ..., am} be the union of all the sets. Given the number k1, the decision problem of the hitting set problem states whether there exists a set A with k1 elements such that every element of S (every set si s.t. i = 1..n) contains at least one element of A. We denote the hitting set problem as HS(S). We construct the weighted DAG G′ from the set S by Algorithm HS2LSTMC. This algorithm considers s as the source vertex of the DAG G′. For each set si of HS s.t. i = 1..n, the algorithm considers the corresponding vertex, si, and adds an edge with infinite weight from s to each si. Then, for each element aj of the union of the input sets s.t. j = 1..m, the algorithm considers the corresponding vertex, aj, and adds an edge with zero weight from each si to any aj s.t. aj ∈si in HS. Finally, the algorithm considers two final vertices called t and k, and add two edges from each aj s.t. j = 1..m to the both final vertices. It is clear that G′ can be made in polynomial time.

Now, we should demonstrate that HS(S) has an answer with k1 elements if and only if LSTMC = (G′, s, t) has an answer with some logically removed edges such that the sum of the weights of the removed edges is k1.

For simplicity, we perform this part of proof, by providing an example:

In the following figure, suppose that S = {s1, s2, s3} such that s1 = {1, 2, 3}, s2 = {1, 4}, and s3 = {2, 5}. Fig. 2 shows the weighted DAG G′ of the LSTMC problem corresponding to the hitting set problem HS(S). In this example, the set A, namely the union of all elements of S, is A = {1, 2, 3, 4, 5}. We have |S| = 3 and |A| = 5. This example shows how an arbitrary instance of the hitting set problem can be solved by the help of a specific instance of the logical s-t min-cut problem in a weighted DAG. If we compute an answer to LSTMC = (G′, s, t) and consider those removed edges of the answer which are in the form of (aj, t) called E1 (1 ≤ j ≤ m), then the tail set of E1 is an answer to HS(S). An answer to the LSTMC problem is the edge set E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. So, the tail set of the subset E2 = {(1, t), (2, t)} of the edge set E1, namely the set {1, 2}, is an answer to the HS(S).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1531