I am using the following definition of the Global Minimum Cut problem: Given a graph $G = (V,E)$, a Cut of $G$ is a partition of $V$ into two subsets $(A,B)$. A cut-edge of $C$ is an edge $(u,v) \in E$, with $u \in A$ and $v \in B$. A Global Minimum Cut of $G$ is a Cut which is the Minimum in some metric.

For my purposes this metric is always considered to be a weight/capacity. For undirected graphs it is well known that the Minimum s-t-Cut from among all s-t-Cuts in the graph is equivalent to the Global Minimum Cut.

I was wondering whether or not the same approach has any application for directed graphs. In this case, it seems to me like a Global Minimum Cut seeks to destroy a graph's weak connectivity, whereas the approach over s-t-Cuts will only ever guarantee the destruction of a graph's strong connectivity. Am I missing anything that would solve this problem?

  • $\begingroup$ @InuyashaYagami I would say that the semantic difference between them is no more than that one is a noun and the other is an adjective. I personally don't find the use problematic, though I wouldn't mind a more specific proposal for improvement. I might just be missing the part that is ambiguous. $\endgroup$ – Vladis Becker May 15 at 15:42
  • 1
    $\begingroup$ @InuyashaYagami I have changed the question as proposed. $\endgroup$ – Vladis Becker May 18 at 12:31
  • $\begingroup$ The statement "minimum s-t-Cut from among all s-t-Cuts in the graph is equivalent to the Global Minimum Cut" is true for directed graphs also. Why do you think it is incorrect? $\endgroup$ – Inuyasha Yagami May 18 at 15:10
  • $\begingroup$ I hope, by the above statement you mean that checking every pair of $(s,t)$ in the graph, and then take the minimum over all min $(s,t)$ cuts, to get global minimum cut. $\endgroup$ – Inuyasha Yagami May 18 at 15:18
  • $\begingroup$ @InuyashaYagami Because my understanding of a minimal-s-t Cut is that it only disconnects s from t. In an undirected graph this is obviously only possible by making the entire graph disconnected. For directed graphs there is the differentiation between the graph being weakly and strongly connected. A strongly connected graph demands that every node is reachable from any other node. A weakly connected graph just demands that all nodes would be reachable from all nodes if the edges were not directed. That second type would definitely be broken by a s-t-Cut, but in my eyes not the first type. $\endgroup$ – Vladis Becker May 19 at 17:47

Your Answer

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

Browse other questions tagged or ask your own question.