patternMinor
Why number of possible cuts in a graph differ from maximum number of minimum cuts?
Viewed 0 times
whynumbermaximumgraphminimumcutspossibledifferfrom
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#76399, answer score: 8
Revisions (0)
No revisions yet.