Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

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

Solutions 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). Furthermore, if we ignore the minimal removal constraint of the 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 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 some DFS in $G$ in polynomial time. Hence, by considering just one of the constraints of LMC problem, it will be solvable polynomially.

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.

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$?
share|improve this question

migrated from stackoverflow.com Apr 27 '12 at 12:43

This question came from our site for professional and enthusiast programmers.

4  
Can you clarify constraint (2)? What exactly cannot you do, and what are some examples of what is allowable? Also, what is a binary DAG? –  Yuval Filmus Apr 27 '12 at 17:06
1  
I don't understand your algorithm with constraint 1 removed, which is presumably an algorithm to find out whether we can disconnect $s$ and $t$ subject to the constraint 2. Can you clarify? –  Yuval Filmus Apr 27 '12 at 21:52
    
I'm pretty sure the problem is in $\mathrm{P}$ if your graph is undirected. Would that be a sufficient answer to your question? –  Alex ten Brink Apr 28 '12 at 6:38
2  
Crosspost: mathoverflow.net/questions/95239/… –  Tsuyoshi Ito Oct 4 '12 at 2:24
1  
Amirv, for the problem with just constraint (2), the algorithm you suggest, as I understand it, is not quite right. There may be a solution even though, for all nodes v, there is a path from s to v and a path from v to t. Consider the graph $G=(V,E)$ with $V=\{s,t,a\}$ and $E=\{(s,t),(s,a),(a,s)\}$. –  Neal Young Nov 21 '12 at 17:45

1 Answer 1

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

share|improve this answer
    
I don't get the following statement: "[arc] 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^∗,t)$ arc." If $a^*$ has only one out-arc, we are not allowed to delete it by definition! By the way, what's with the $\{a^*\}$ notation? –  Pål GD Jan 16 '13 at 15:44
    
Ah - I misread a comment about the second condition. It's not an integral part of the algorithm though -- if we cannot delete single out-arcs, we just don't. Skip it and move on the reverse-transitive-closure ordering. You either reach a vertex with two out-arcs or $s$ (if so, output "no solution"). The $\{a*\}$ notation is because I'm thinking of the current collection of maximal vertices (generally speaking, there is more than 1 such vertex at a time, since a transitive closure is a partial ordering). Also, using just $a$ seemed to imply an arbitrary element of $A$, which is not intended. –  Daniel Apon Jan 17 '13 at 2:19
    
Dear Daniel, you should formally prove that why your suggested algorithm is correct, namely, why your greedy algorithm gives the optimal (minimal) answer. In fact, it is not clear, at least for me, why it works correctly. However, I verified your solution. It seems that it does not give the correct (optimal, namely minimal) answer. As a counter example, consider the following DAG G. Let V={s,v1,v2,v3,t} and E={(s,v1),(s,v2),(v1,v3),(v1,t),(v3,v2),(v3,t)}. According to your algorithm, the answer is the removal of E1={(v1,t),(v3,t)}, but the real answer is the removal of E2={(s,v1)} from E(G). –  amirv Jan 18 '13 at 7:40
    
amirv, I apologize for the lack of formal proof. Can you construct an example that doesn't involve an $(s, v)$ directed edge? If you define a new start vertex $S$ and let $s$ be $v_0$, then $v_0\in A$, and the (unchanged) algorithm finds the minimum path you describe. (Namely, $v_0$ is the final vertex in the reverse transitive ordering, and since it has an edge to $A$ and the other to $B$, the greedy question is whether to delete the one to $B$ or not. In this case, repeating the search as prescribed shows that deleting this single edge beats the two edges previously considered.) –  Daniel Apon Jan 18 '13 at 8:21
    
Basically, this seems like a degenerate case that avoids the actual work of the algorithm by using the start vertex. (Zero doubt the algorithm could be better written, fwiw.) If the algorithm is going to fail, I suspect it will be because of odd interactions involving the partial order component (causing the problem to not decompose so cleanly as I've suggested it does). –  Daniel Apon Jan 18 '13 at 8:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.