In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in weight). How do I do that?

Are you familiar with the randomized contraction algorithm also known as Karger's algorithm? The algorithm basically works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

What I suggest now is that you run the randomized contraction algorithm several times. Each time the algorithm outputs a cut, decide whether or not to keep it by checking if it is small enough. Naturally you can halt when you have produced enough of these small enough cuts. Depending on the size of your input, this might even work quite well in practice.

StackExchange Computer Science Q#2052, answer score: 3