24
$\begingroup$

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$?
$\endgroup$
  • $\begingroup$ I'm pretty sure the problem is in $\mathrm{P}$ if your graph is undirected. Would that be a sufficient answer to your question? $\endgroup$ – Alex ten Brink Apr 28 '12 at 6:38
  • $\begingroup$ @SaeedAmiri: find a min-cut for $s$ and $t$. If it disconnects a vertex, then this vertex must be $s$ or $t$. If it's both, then there is no such min cut. Suppose $t$ is the disconnected vertex and $(t,v)$ the edge. Remove this edge and perform a min-cut on $s$ and $v$ recursively. $\endgroup$ – Alex ten Brink Apr 28 '12 at 17:50
  • $\begingroup$ By a simple observation, it can be concluded that if the following problem is NP-Complete then the LMC problem will be NP-Complete too (I'm not ensure the inverse is true). Suppose that $G=(V,E)$ is a digraph. How we can have a min-cut on $G$ (partition $V$ to $S$ and $T$ s.t. the number of edges from $S$ to $T$ is minimal) and there does not exist a vertex $v$ belong to $V$ s.t. the head of every exit edge of $v$ belongs to $T$ (the exit edge is from $S$ to $T$). $\endgroup$ – amirv Apr 29 '12 at 6:43
  • 2
    $\begingroup$ Crosspost: mathoverflow.net/questions/95239/… $\endgroup$ – Tsuyoshi Ito Oct 4 '12 at 2:24
  • 2
    $\begingroup$ 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)\}$. $\endgroup$ – Neal Young Nov 21 '12 at 17:45
1
$\begingroup$

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

Reduction

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Pål GD Jan 16 '13 at 15:44
  • $\begingroup$ 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. $\endgroup$ – Daniel Apon Jan 17 '13 at 2:19
  • 2
    $\begingroup$ I finally managed to prove that this problem is NP-Complete. $\endgroup$ – amirv May 7 '16 at 10:31
  • 1
    $\begingroup$ @amirv Oh, please do share an outline of the proof in the form of an answer! $\endgroup$ – Raphael Aug 31 '16 at 21:38
  • 1
    $\begingroup$ The problem is NP-Complete, even if the underlying digraph is an unweighted binary DAG. $\endgroup$ – amirv Feb 8 '17 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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