Find minimum cut in a graph such that given vertices are disconnected

8
votes

Some time ago I read about the general mininum cut algorithm that takes as input a graph and removes a min. number of edges such that two disconnected components remain.

I am now working on an undirected graph with 10k+ nodes and 500k+ edges (no multiple edges between two vertices). To attribute interactions between nodes I thought about computing the minimum cut disconnecting two given vertices (or flow-related measures).

Are there efficient algorithms to come up with a value (cardinality of the min. cut set) for every pair of vertices in the graph? Being rather new to the topic, I would be deeply grateful if anyone could provide links to papers or other resources outlining algorithms which operate at a reasonable run-time complexity.

Thanks!

1
graphgraph-theory

1 Answers

8
votes

There are several algorithms (see Wiki for an introduction) that find a maximum flow in a network. Those I know (Ford-Fulkerson, Dinic, Karp-Edmond) should perform well for unit capacity ( = integer capacity equal to 1 on all edges) (variable capacities increase complexity and more problems arise with non-integer capacities)

For any pair of of vertices, you create a network from the graph by setting source/sink to this pair. You get the maximum flow using one of the algorithms, which you use to get the cut as follows:

  • Choose any edge used by the flow. This edge will belong to the cut.
  • Repeat, but now do the flow search on a graph without selected edge(s) until the flow is 0

In the end, you have the minimum cut, size of the maximum flow.

If you really want to press on the performance, you might want to have a look at this paper: Flows in Undirected Unit Capacity Networks (1997) by Andrew V. Goldberg, Satish Rao, but I'd probably stick with the simpler ones.