5
$\begingroup$

According to this wikipedia link, under the title "Success probability of the contraction algorithm": Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\choose{2}$, where $n$ is number of vertices.

My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a candidate minimum cut?

$\endgroup$
5
$\begingroup$

In a specific graph, not any cut is a minimum cut. What Wikipedia claims is that out of the $2^{n-1}-1$ potential cuts, at most $\binom{n}{2}$ can be minimum cuts in any given graph. Some graphs contain even fewer minimum cuts. For example, if you connect two cycles by a single edge then there is a unique minimum cut.

The upper bound on the number of minimum cuts follows by analyzing Karger's algorithm (linked to in the question): you can show that the probability that the algorithm produces any specific minimum cut is at least $1/\binom{n}{2}$, and so there can be at most $\binom{n}{2}$ of them.

$\endgroup$

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.