Is Logical Min-Cut NP-Complete?

Question

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$?

Answer 1

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

Answer 2

Here's (an attempt at) a polynomial-time algorithm for LMC on arbitrary binary DAGs $G$.

This answers Question #3. (Sorry for the messy write-up ahead of time. :))

To begin, throw out "forever" any vertex not reachable from $s$. We don't care about these, since they're not part of any $s$-$t$ path.

Next, define sub-DAGs $A$ and $B$, initially empty. Then, for all vertices $v \in G-\{s, t\}$,

Test whether there is a path from $v$ to $t$. If so, add $v$ to $A$. If not, add $v$ to $B$.

Let the edges of $A$ and $B$ be those induced by the vertices within each set (for now, ignore any edges from $s$ to $A$, from $A$ to $t$, and from $A$ to $B$; also note there are no edges from $B$ to $t$ by construction).

Then, compute the transitive closure of $A$. Namely, we are interested in finding some set of vertices $\{a^*\}$ that are the "leaves" of the sub-DAG $A$.

Fix any such $a^*$. Observe that there must be a directed edge from $a^*$ to $t$. This is because, by construction, (i) there is an $s$-$t$ path through $a^*$, (ii) there are no paths from $a^*$ through $B$, and (iii) since $A$ is itself a DAG and $a^*$ is a leaf of $A$, there is no path from $a^*$ through another vertex of $A$ to $t$.

Now, there must also be a directed edge from each vertex in $\{a^*\}$ to some vertex in $B$, or some of the $\{a^*\}$ have a single edge to $t$. In either case, we are allowed to delete any $a^*\rightarrow t$ edge.

If $|\{a^*\}|$ = 1, then either we must delete the edge from the unique $a^*\rightarrow t$, or there is a vertex earlier in the $s$-$t$ path containing $a^*$ that has two paths to $t$ -- one through $a^*$ and one directly. In case that the latter might hold, we record $a^*\rightarrow t$ and proceed "backwards greedily" (details on this below).

If $|\{a^*\}|$ > 1, then we must either delete all of the edges from $\{a^*\}\rightarrow t$, or else there are some number of edges $k < |\{a^*\}|$ earlier in the transitive closure of $A$ that disconnect all paths from $s$ through the $\{a^*\}$ to $t$.

This is where we use the fact that the graph $G$ is a binary DAG.

Consider the set of predecessors of $\{a^*\}$. Since each of these vertices has out-degree at most two, there are exactly three cases:

Case 1. A predecessor has an out-edge to some vertex in $\{a^*\}$ and an out-edge to some vertex in $B$.

In this case, it doesn't matter whether we delete the edge from the predecessor to the vertex in $\{a^*\}$ or the edge from the vertex in $\{a^*\}$ to $t$. Therefore, we can "skip past" this vertex (and check whether the backwards path merges with a path of another vertex in $\{a^*\}$).

Case 2. A predecessor has an out-edge to a vertex in $\{a^*\}$ and another predecessor of the $\{a^*\}$.

In this case, we must either delete both edges from the $\{a^*\}$ to $t$, or we can delete a single earlier edge in the path from $s$ to the predecessor that disconnects both paths.

Case 3. A predecessor has an out-edge to two vertices in $\{a^*\}$.

This is identical to case 2. It doesn't matter whether we delete one of this predecessor's edges and the corresponding other edges from $\{a^*\}$ to $t$, or both of the edges from the $\{a^*\}$ to $t$. We just want to know whether we can disconnect the path from $s$ through this predecessor to $t$ with a single edge earlier in the path from $s$ to the predecessor.

Altogether, as we scan backwards through predecessors in the transitive closure of $A$, we can greedily keep track of the "best so far" choices. That is, at every step, we have an obvious choice that involves deleting some number of edges, but we want to wait to see whether a better option is available. Once a better option is found, we can "forget" about the previous option. Hence, a greedy choice at each layer of predecessors suffices (so long as we wait until the end to commit to any choice).

Therefore, with some basic memoization, the time and space complexities of this process appear to be at most $O(|E|)$. This leaves out the fact that, while we can locally/greedily identify when we have found a "cheaper choice," it's a priori unclear which previously-recorded edges to remove. Therefore, we record the order in which we check edges as we go. Upon finding a better option, we repeat the search up to this point in order to find which previously-recorded edges to remove. The total time complexity of this step is $O(|E|^2)$ and space complexity $O(|E|)$.

Altogether, the time complexity is $O(|V|\cdot(|V|+|E|))$ for initialization, plus $O(|V|^3)$ for the transitive closure, plus $O(|E|^2)$ for the search. The total time is $O(|V|^2+|E||V|+|V|^3+|E|^2) = {\bf O(|V|^3+|E|^2)}$.

Upon completing the process, we obtain the minimum set of edges required to disconnect $s$ from $t$ while preserving at least one out-edge of every vertex in the graph (or we discover that a solution is impossible along the way, and abort).