2

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.

user2844647
  • 163
  • 4
  • Collapse the two sets to a meta node. – Nico Schertler Mar 31 '16 at 06:36
  • +Nico could you elaborate? – user2844647 Mar 31 '16 at 19:09
  • 1
    It's basically a similar approach as Sorin described in his answer. But instead of linking the vertices from the two sets to the new source and sink nodes, I would have replaced them. Btw, the weights are not restricted to be 1. So you can use Sorin's approach with any other weight configuration. – Nico Schertler Mar 31 '16 at 20:11

1 Answers1

1

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.

Sorin
  • 11,863
  • 22
  • 26
  • Yes the max flow algorithm could work but I have edges with positive fractional weights, that I cannot make 1. Apart from that major constraint, this is exactly what I need. – user2844647 Mar 31 '16 at 19:08
  • @user2844647 You can run max flow in this case as well. Change the path finding algorithm to find the one with the largest capacity and stop when the capacity added is less than some epsilon (say, 1e-3). – Sorin Apr 01 '16 at 11:29