Randomized Min-Cut Analysis
Karger's Min-Cut Algorithm finds a minimum cut in an undirected multigraph $G = (V, E)$ with $n$ vertices:
while |V| > 2:
Pick an edge (u, v) uniformly at random
Contract (u, v): merge u and v into a single vertex
Remove all self-loops
return the edges between the two remaining verticesRecall from the analysis that the probability of finding a specific minimum cut $C$ in a single run is at least $\frac{2}{n(n-1)} = \frac{1}{\binom{n}{2}}$.
Part A
A graph may have several different minimum cut sets. Using the analysis of the randomized min-cut algorithm, what is the maximum number of distinct min-cut sets that a graph with $n$ vertices can have?
Let $C_1, C_2, \ldots, C_m$ be all distinct minimum cut sets in $G$.
Key observation: The events "algorithm outputs $C_i$" are mutually exclusive (only one cut can be output per run).
From the analysis, $\Pr[\text{output } C_i] \geq \frac{2}{n(n-1)}$ for each $i$.
Since probabilities of disjoint events sum to at most 1:
Tight example: The cycle graph $C_n$ achieves this bound. Every pair of edges forms a min-cut (of size 2), and there are exactly $\binom{n}{2}$ such pairs.
Part B
An $r$-way cut-set is a set of edges whose removal breaks the graph into $r$ or more connected components. The randomized min-cut algorithm can be adapted to find minimum $r$-way cut-sets by contracting until $r$ vertices remain (instead of 2).
What is the probability that this adapted algorithm finds a specific minimum $r$-way cut in one iteration?
Adapted algorithm: Contract until $r$ vertices remain. The edges between the $r$ remaining super-vertices form an $r$-way cut.
Analysis: Let $C$ be a minimum $r$-way cut of size $k$. Every vertex has degree $\geq k$ (otherwise removing fewer edges could separate it).
At step $i$ (with $n - i$ vertices remaining), we need $n - i > r$:
The algorithm runs for $n - r$ contraction steps (reducing from $n$ to $r$ vertices).
Success probability:
Note: For $r = 2$, this gives $\frac{1}{\binom{n}{2}} = \frac{2}{n(n-1)}$, matching the original analysis.
Implication: Larger $r$ means higher success probability (since $\binom{n}{r}$ is largest around $r = n/2$). Finding 3-way cuts is easier than 2-way cuts!
Hints
If there were more than $\binom{n}{2}$ distinct min-cuts, what would that imply about the sum of their individual success probabilities?
Generalize the original analysis: at step $i$, the probability of not contracting a cut edge is $\frac{n-i-r}{n-i}$ (instead of $\frac{n-i-2}{n-i}$).