7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is small in weight? How many cuts do you want, a constant number, $n$, $n^2$? $\endgroup$ – utdiscant May 24 '12 at 20:23
  • 1
    $\begingroup$ 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. $\endgroup$ – steph May 24 '12 at 20:31
  • $\begingroup$ @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. $\endgroup$ – Raphael May 25 '12 at 11:22
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ By doing a depth-first search instead of randomisation, this can also be used to get all minimial cuts or, alternatively, increasing the chances to find new cuts in every iteration. $\endgroup$ – Raphael Jul 4 '12 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.