# 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?

• What is small in weight? How many cuts do you want, a constant number, $n$, $n^2$? – utdiscant May 24 '12 at 20:23
• To make it simple, all edges has a weight of 1 and small means "the number of edges of a cut be small, say less than 10 for example.". I want about n cuts, for example. or just several hundreds, whichever eases the design. thanks. – steph May 24 '12 at 20:31
• @steph: Note that for unit weights, the problem likely collapses to a conceptually simpler one, so a solution might not help you in the general case. – Raphael May 25 '12 at 11:22