On this page

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 vertices

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

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?

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}$ ).