I have an undirected weighted graph and I need to find the minimum cut that separates two sets of vertices. I can modify my setup so as to reduce the problem to finding the minimum cut that separates two given vertices. I want to add that the weights are positive and fractional.
The Stoer–Wagner algorithm does everything except keeping specified nodes on different sides of the cut, and I was curious if there's any way of modifying SW to do that.
Thank you.
Not sure about Stoer-Wagner, but another tipical way of solving this problem is with MaxFlow.
You link one set of nodes to the source, the other to the destination with infinite capacity. Every other edge should have a weight of 1, then do MaxFlow in the resulting graph.
When you are done mark all the nodes that are still accessible from the source in the residual network (the nodes visited on the last path finding run). Any edge that goes between a marked and unmarked node in the original graph is part of the minimum cut.