Is there an algorithm to find minimum cut in undirected graph separating source and sink

4
votes

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components.

I know about Ford-Fulkerson's maximum flow algorithm and his theorem about maximum flow and minimum cut relation on directed graphs.

I also know about a modification of Ford-Fulkerson's maximum flow algorithm for undirected graphs, which replaces each undirected edge with 2 opposite directed edges and updates flow to both of them simultaneously. But with this modification, the max-flow-min-cut-theorem seems to not be valid anymore, because on the following undirected graph the minimum cut will not be determined correctly:

nodes: 0, 1, 2, 3
edges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4
source: 0
sink: 3

The max-flow-min-cut theorem says, minimum cut are those edges, which flow is equal to their capacity, and by the modified Ford-Fulkerson that's all the edges, which is obviously not the correct cut.

I found a Stoer–Wagner algorithm for finding a global minimum cut in undirected graph, but that's quite not the thing i want, since this algorithm doesn't consider any source and sink, and can find a cut, which lets the nodes be in the same component.

Is there any algorithm, which can efficiently find a minimum cut in an undirected graph with source and sink, separating these 2 specified nodes? Can i maybe somehow modify the previously mentioned algorithms to make them working for my case?

2
algorithmgraph-algorithmgraph-theorynetwork-flow
How about converting your graph to a directed graph by replacing each undirected edge by 2 edges for each direction? – Sam Segers
@SamSegers: That works for flows, but won't work for cuts anymore, i will try to put more info about this into question – Youda008
@Youda008: Why wouldn't this work for finding the cut itself? – SivanBH

2 Answers

0
votes

You can use some modification of the Ford-Fulkerson's algorithm.

  1. Firstly you need to find maximum flow between source and sink and rememver it.
  2. Remove some edge from the graph.
  3. Then you need to find maximum flow in the new graph. If maximum flow is not the same as on step one then this edge is in the minimal cut.
  4. Return edge to the graph, choose some another edge and go to step 2.

When you finding maximal flow, just consider undirected edge as two directed edges with same capacity.

0
votes

The max-flow-min-cut theorem says, minimum cut are those edges, which flow is equal to their capacity ...

This is not correct. You have already given a counterexample. A correct algorithm to find a min cut from a max flow is given in this post. I quote it here.

The minimum cut is a partition of the nodes into two groups.

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition A. The rest of the nodes (the unreachable ones) can be called B. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in A to a node in B.

So, as you said, you can transform each edge into 2 opposite directed edges, compute the max flow in the new graph, then use the algorithm above to transform the max flow to a min cut.