COMPX270 — Randomised and Advanced Algorithms
Chapter 5: Graph Algorithms
Randomised graph algorithms: Karger’s min-cut via random contraction, the Karger-Stein speed-up, counting minimum cuts, and minimum spanning trees in expected linear time.
Graph contraction identities, telescoping products, MST properties, and recurrence solutions
Karger’s Min-Cut Algorithm
The Min-Cut Problem
Given a connected undirected multigraph \(G = (V, E)\) with \(|V| = n\) vertices and \(|E| = m\) edges, a cut is a partition of \(V\) into two non-empty sets \((S, \bar{S})\). The size of the cut is the number of edges crossing it:
\[c(S, \bar{S}) = |\{e \in E : e \text{ has one endpoint in } S \text{ and one in } \bar{S}\}|\]The minimum cut (min-cut) is a cut of smallest size. Let \(k\) denote the min-cut value.
Fact 25.1
The global min-cut can be computed by solving \(n - 1\) max-flow instances (one for each choice of sink, with a fixed source). Via the max-flow min-cut theorem, this gives the global minimum cut. Using the fastest max-flow algorithms, this takes \(O(mn \log(n^2/m))\) time.
Edge Contraction
Definition 25.1 (Edge Contraction)
Given a multigraph \(G = (V, E)\) and an edge \(e = \{u, v\}\), the contraction of \(e\) produces a new graph \(G / e\) by:
- Merging \(u\) and \(v\) into a single “super-vertex” \(uv\).
- Every edge that was incident to \(u\) or \(v\) (other than \(e\) itself) becomes incident to \(uv\).
- All self-loops on \(uv\) are removed.
Parallel (multi-) edges are retained. The contracted graph has \(|V| - 1\) vertices.
Algorithm 10: Karger’s Random Contraction
Input: Connected multigraph \(G = (V, E)\)
- While \(|V| > 2\):
- Pick an edge \(e \in E\) uniformly at random.
- Contract \(e\): replace \(G\) by \(G / e\).
- Return the cut defined by the two remaining super-vertices.
Intuition
The algorithm only fails if it contracts an edge that crosses the min-cut. Since the min-cut has \(k\) edges out of \(|E|\) total edges, small cuts are less likely to be destroyed. The key insight: at every step, the graph has many edges (at least \(nk/2\) initially by the min-degree bound), so each individual min-cut edge has a small probability of being selected.
Theorem 26
For any specific min-cut \(C\) in a multigraph \(G\) on \(n\) vertices, Karger’s algorithm (Algorithm 10) returns \(C\) with probability at least:
\[\Pr[\text{output} = C] \geq \frac{2}{n(n-1)} = \binom{n}{2}^{-1}\]Let \(C\) be a specific min-cut of size \(k\). The algorithm performs \(n - 2\) contractions. Let \(\mathcal{E}_i\) be the event that the \(i\)-th contraction does not contract an edge of \(C\). The algorithm returns \(C\) if and only if all \(\mathcal{E}_1, \mathcal{E}_2, \ldots, \mathcal{E}_{n-2}\) occur.
Key bound on \(|E_i|\): After \(i - 1\) contractions, the graph \(G_i\) has \(n_i = n - (i - 1)\) vertices. Since contractions never decrease the min-cut value, the min-cut of \(G_i\) is still at least \(k\). Therefore every vertex in \(G_i\) has degree at least \(k\). By the handshaking lemma:
\[2|E_i| = \sum_{v \in V_i} \deg(v) \geq n_i \cdot k = (n - i + 1) \cdot k\]So \(|E_i| \geq (n - i + 1)k / 2\).
Conditional probability: Given that \(\mathcal{E}_1, \ldots, \mathcal{E}_{i-1}\) all occurred (so the \(k\) edges of \(C\) are still present), the probability of contracting a \(C\)-edge in step \(i\) is:
\[\Pr[\overline{\mathcal{E}_i} \mid \mathcal{E}_1 \cap \cdots \cap \mathcal{E}_{i-1}] = \frac{k}{|E_i|} \leq \frac{k}{(n - i + 1)k/2} = \frac{2}{n - i + 1}\]Therefore:
\[\Pr[\mathcal{E}_i \mid \mathcal{E}_1 \cap \cdots \cap \mathcal{E}_{i-1}] \geq 1 - \frac{2}{n - i + 1} = \frac{n - i - 1}{n - i + 1}\]Telescoping product:
\[\Pr[\mathcal{E}_1 \cap \cdots \cap \mathcal{E}_{n-2}] = \prod_{i=1}^{n-2} \Pr[\mathcal{E}_i \mid \mathcal{E}_1 \cap \cdots \cap \mathcal{E}_{i-1}] \geq \prod_{i=1}^{n-2} \frac{n - i - 1}{n - i + 1}\]Writing this out:
\[= \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdot \frac{n-5}{n-3} \cdots \frac{2}{4} \cdot \frac{1}{3}\]This is a telescoping product. The numerator is \((n-2)!\) divided by \((n-2)(n-3) = (n-2)!\) from the top, and the denominator similarly telescopes. The result is:
\[= \frac{2}{n(n-1)} = \binom{n}{2}^{-1} \quad \square\]Algorithm 11: Best-of-\(T\) Repetition
Input: Connected multigraph \(G = (V, E)\), number of trials \(T\)
- Repeat \(T\) times: run Algorithm 10, record the cut found.
- Return the smallest cut among all \(T\) trials.
Theorem 27
Running Algorithm 10 for \(T = \binom{n}{2} \ln(1/\varepsilon)\) independent trials, the probability of not finding the min-cut is at most \(\varepsilon\). The total running time is:
\[O\!\left(n^4 \log \frac{1}{\varepsilon}\right)\]In particular, setting \(\varepsilon = 1/n\) gives \(O(n^4 \log n)\) time with high probability.
Each trial fails with probability at most \(1 - 2/(n(n-1))\). After \(T\) independent trials:
\[\Pr[\text{all fail}] \leq \left(1 - \frac{2}{n(n-1)}\right)^T \leq e^{-2T/(n(n-1))}\]Setting \(T = \binom{n}{2} \ln(1/\varepsilon) = \frac{n(n-1)}{2} \ln(1/\varepsilon)\):
\[\Pr[\text{all fail}] \leq e^{-\ln(1/\varepsilon)} = \varepsilon\]Each trial takes \(O(n^2)\) time, so total time is \(O(n^2 \cdot n^2 \ln(1/\varepsilon)) = O(n^4 \log(1/\varepsilon))\). \(\square\)
Interactive: Karger’s Min-Cut Simulation
Generate a random graph and run Karger’s contraction algorithm. Observe how the success rate compares to the theoretical bound \(2/(n(n-1))\).
Interactive: Edge Contraction Step-by-Step
Watch Karger’s contraction in action on a small graph. Pick a random edge, merge its endpoints into a super-node, and observe the multigraph evolve. When only 2 super-nodes remain the cut is revealed.
Karger-Stein Algorithm
Motivation: Where Karger Loses Probability
In Karger’s algorithm, the early contractions are relatively safe — the probability of hitting a min-cut edge is small when the graph still has many vertices. The danger is in the last few steps: when only 3 vertices remain, the probability of destroying the min-cut in the next contraction is \(2/3\).
Key idea: Contract down to \(\lceil n/\sqrt{2} \rceil + 1\) vertices (where survival probability is still \(\geq 1/2\)), then branch into two independent recursive calls and take the better result.
Algorithm 12: Karger-Stein
Procedure \(\text{ModifiedKarger}(G, t)\):
- While \(|V(G)| > t\): pick a random edge, contract it.
- Return the resulting graph.
Procedure \(\text{KargerStein}(G)\):
- If \(|V(G)| \leq 6\): find the min-cut by brute force and return it.
- Set \(t = \lceil |V(G)| / \sqrt{2} \rceil + 1\).
- \(G_1 \leftarrow \text{ModifiedKarger}(G, t)\).
- \(G_2 \leftarrow \text{ModifiedKarger}(G, t)\) (independent random choices).
- Return \(\min(\text{KargerStein}(G_1),\; \text{KargerStein}(G_2))\).
Running Time Analysis
The contraction from \(n\) vertices down to \(\approx n/\sqrt{2}\) takes \(O(n^2)\) time. The recurrence is:
\[T(n) = 2 \cdot T\!\left(\frac{n}{\sqrt{2}}\right) + O(n^2)\]Let \(n_j = n / (\sqrt{2})^j\). At depth \(j\) there are \(2^j\) subproblems, each of size \(n_j\), costing \(O(n_j^2)\) each. The total work at depth \(j\) is:
\[2^j \cdot O\!\left(\frac{n^2}{2^j}\right) = O(n^2)\]The recursion depth is \(O(\log n)\) (until \(n_j \leq 6\)), so the total running time is:
\[T(n) = O(n^2 \log n)\]Success Probability Analysis
From the proof of Theorem 26, contracting from \(n\) vertices down to \(t = \lceil n/\sqrt{2} \rceil + 1\) vertices preserves a specific min-cut with probability at least:
\[\prod_{i=1}^{n - t} \frac{n - i - 1}{n - i + 1} \geq \frac{t(t-1)}{n(n-1)} \geq \frac{1}{2}\]Let \(p(n)\) be the probability that KargerStein finds the min-cut. The two branches are independent, so:
\[p(n) \geq 1 - \left(1 - \frac{1}{2} \cdot p\!\left(\frac{n}{\sqrt{2}}\right)\right)^2\]Claim 27.1
Define \(f(t)\) by the recurrence \(f(0) = 1\) and \(f(t) \geq 1 - (1 - f(t-1)/2)^2\). Then \(f(t) \geq \frac{1}{t + 2}\) for all \(t \geq 0\).
Base case: \(f(0) = 1 \geq 1/2\). \(\checkmark\)
Inductive step: Assume \(f(t-1) \geq 1/(t+1)\). Then:
\[f(t) \geq 1 - \left(1 - \frac{f(t-1)}{2}\right)^2 \geq 1 - \left(1 - \frac{1}{2(t+1)}\right)^2\]Expanding:
\[= 1 - 1 + \frac{1}{t+1} - \frac{1}{4(t+1)^2} = \frac{1}{t+1} - \frac{1}{4(t+1)^2}\] \[= \frac{1}{t+1}\left(1 - \frac{1}{4(t+1)}\right) = \frac{4(t+1) - 1}{4(t+1)^2} = \frac{4t + 3}{4(t+1)^2}\]We need to show \(\frac{4t+3}{4(t+1)^2} \geq \frac{1}{t+2}\), i.e., \((4t+3)(t+2) \geq 4(t+1)^2\):
\[(4t+3)(t+2) = 4t^2 + 11t + 6 \geq 4t^2 + 8t + 4 = 4(t+1)^2\]This holds since \(11t + 6 \geq 8t + 4\) for all \(t \geq 0\). \(\square\)
Theorem 28
The Karger-Stein algorithm (Algorithm 12) runs in \(O(n^2 \log n)\) time and finds any specific min-cut with probability \(\Omega(1/\log n)\).
Corollary 28.1
Running Karger-Stein \(T = O(\log n \cdot \log(1/\varepsilon))\) times and taking the best cut, we find the min-cut with probability \(\geq 1 - \varepsilon\) in total time:
\[O\!\left(n^2 \log^2 n \cdot \log \frac{1}{\varepsilon}\right)\]This is a significant improvement over the \(O(n^4 \log(1/\varepsilon))\) of repeated Karger.
Counting Minimum Cuts
A Structural Result from Algorithm Analysis
A beautiful feature of Karger’s algorithm: the analysis of its success probability yields a purely graph-theoretic result about the number of distinct minimum cuts. The algorithm never “knew” about this bound — it fell out of the probability calculation.
Theorem 29
Any connected multigraph on \(n\) vertices has at most \(\binom{n}{2} = \frac{n(n-1)}{2}\) distinct minimum cuts.
Let \(M\) be the number of distinct minimum cuts. By Theorem 26, each specific min-cut \(C_j\) is returned by Karger’s algorithm with probability \(\geq 1/\binom{n}{2}\). Since the events “algorithm returns \(C_j\)” for different \(j\) are mutually exclusive (the algorithm returns exactly one cut), we have:
\[1 \geq \sum_{j=1}^{M} \Pr[\text{output} = C_j] \geq M \cdot \frac{1}{\binom{n}{2}}\]Therefore \(M \leq \binom{n}{2}\). \(\square\)
Tightness: The Cycle Graph
The bound \(\binom{n}{2}\) is tight. Consider the cycle graph \(C_n\) on \(n\) vertices. The min-cut has value \(k = 2\) (remove any two edges to disconnect). Each min-cut corresponds to choosing 2 of the \(n\) edges to remove, and there are exactly \(\binom{n}{2}\) ways to do this, each producing a distinct minimum cut.
Contrast: Total Number of Cuts
A graph on \(n\) vertices has \(2^{n-1} - 1\) cuts in total (each non-trivial partition \((S, \bar{S})\) with \(S \neq \emptyset\) and \(\bar{S} \neq \emptyset\), counted up to symmetry). The fact that only \(O(n^2)\) of these can be minimum cuts is remarkable — it means minimum cuts are an extremely sparse subset of all possible cuts.
MST in Expected Linear Time
The MST Problem
Given a connected undirected graph \(G = (V, E)\) with edge weights \(w : E \to \mathbb{R}\), find a spanning tree \(T\) of minimum total weight \(w(T) = \sum_{e \in T} w(e)\).
Known Deterministic Algorithms
| Algorithm | Time Complexity |
|---|---|
| Kruskal | \(O(m \log n)\) |
| Prim (with Fibonacci heap) | \(O(m + n \log n)\) |
| Borůvka | \(O(m \log n)\) |
| Fredman–Tarjan | \(O(m \log^* n)\) |
| Chazelle | \(O(m \cdot \alpha(m, n))\) |
None of these achieves \(O(m)\). The Karger–Klein–Tarjan (KKT) algorithm achieves expected \(O(m)\) time using randomisation.
Building Block 1: Cut Property & Cycle Property
Cut Property
For any cut \((S, \bar{S})\), the lightest edge crossing the cut must be in every MST (assuming unique edge weights).
Cycle Property
For any cycle \(C\) in \(G\), the heaviest edge on \(C\) is not in any MST (assuming unique edge weights).
Building Block 2: \(F\)-Heaviness
Definition 29.1 (\(F\)-Heavy and \(F\)-Light Edges)
Let \(F\) be a forest on the vertex set \(V\). An edge \(e = \{u, v\} \in E\) is called \(F\)-heavy if \(u\) and \(v\) are connected in \(F\) and \(w(e)\) is strictly greater than the maximum weight edge on the path from \(u\) to \(v\) in \(F\). Otherwise, \(e\) is \(F\)-light.
By the cycle property, \(F\)-heavy edges (with respect to any MST \(F\)) cannot be in the MST. So we only need to consider \(F\)-light edges.
Building Block 3: Borůvka Steps
A single Borůvka step does the following: for each vertex (or component), select the lightest edge leaving the component, then contract all selected edges. This:
- Reduces the number of vertices by at least a factor of 2.
- Takes \(O(m)\) time.
- After \(t\) Borůvka steps: at most \(n / 2^t\) vertices remain.
Building Block 4: Random Subsampling
Include each edge of \(G\) independently with probability \(p\) to form a subgraph \(G' = (V, E')\). Then \(\mathbb{E}[|E'|] = pm\).
Lemma 29.1 (Random Subsampling Lemma)
Let \(G = (V, E)\) be a graph with edge weights. Sample each edge independently with probability \(p\) to get \(G'\). Let \(F'\) be the MST of \(G'\). Then the expected number of \(F'\)-light edges in \(G\) is at most \(|V| / p\).
Order all edges by weight: \(e_1, e_2, \ldots, e_m\). Process them in this order. Edge \(e_i\) is \(F'\)-light if and only if it connects two different components of \(F'\), i.e., adding \(e_i\) to \(F'\) would not create a cycle with a heavier edge already in \(F'\).
Consider the moment we process edge \(e_i = \{u, v\}\). It is \(F'\)-light if either \(u\) and \(v\) are in different components of \(F'\), or \(e_i\) is lighter than the heaviest edge on the \(u\)–\(v\) path in \(F'\). By the structure of the random sampling:
Each edge that would have “blocked” \(e_i\) (i.e., lighter edges connecting the same components) was included in \(G'\) independently with probability \(p\). The expected number of \(F'\)-light edges can be bounded by a charging argument: each light edge can be “charged” to a vertex, and each vertex is charged at most \(1/p\) times in expectation. Total: \(|V|/p\). \(\square\)
Fact 29.1 (MST Verification)
Given a graph \(G = (V, E)\) and a spanning tree \(T\), we can determine all \(T\)-heavy edges in \(O(m + n)\) time. (Due to King, 1997.)
Algorithm 14: KKT Algorithm for MST
Input: Connected graph \(G = (V, E)\) with edge weights
- Borůvka: Apply \(t\) Borůvka steps to reduce to \(\leq n/2^t\) vertices. Let \(G_1\) be the result.
- Subsample: Include each edge of \(G_1\) independently with probability \(p\) to get \(G'\).
- Recursive MST of sample: Recursively compute the MST \(F'\) of \(G'\).
- Identify light edges: Using \(O(m + n)\) MST verification, find all \(F'\)-light edges in \(G_1\). Let \(G_2\) be the subgraph of \(G_1\) consisting of these light edges.
- Recursive MST of light edges: Recursively compute the MST of \(G_2\).
- Return the MST edges found (including edges from Borůvka steps).
Setting the Parameters
Choose \(t = 3\) Borůvka steps and \(p = 1/2\). After Borůvka, we have \(n' \leq n/8\) vertices and still \(\leq m\) edges. The two recursive calls are:
- First call (on \(G'\)): expected \(m/2\) edges, \(n/8\) vertices.
- Second call (on \(G_2\)): by Lemma 29.1, expected \(\leq 2 \cdot n/8 = n/4\) edges, \(n/8\) vertices.
The expected-time recurrence is:
\[T(m, n) \leq T(m/2,\, n/8) + T(n/4,\, n/8) + O(m + n)\]One can verify that \(T(m, n) = O(m + n)\) satisfies this recurrence.
Theorem 30
The KKT algorithm computes the MST of a connected graph with \(n\) vertices and \(m\) edges in expected \(O(m)\) time.
This is a Las Vegas algorithm: it always returns the correct MST; only the running time is random.
The correctness follows from the cut property: Borůvka steps add MST edges, and after removing \(F'\)-heavy edges (which cannot be in the MST by the cycle property), the MST of the remaining light-edge subgraph gives the remaining MST edges.
For the running time, let \(T(m, n)\) be the expected time. With \(t = 3\) and \(p = 1/2\):
\[T(m, n) \leq T(m/2, n/8) + T(n/4, n/8) + c(m + n)\]Guess \(T(m, n) \leq a(m + n)\) for some constant \(a\). Substituting:
\[a(m + n) \leq a(m/2 + n/8) + a(n/4 + n/8) + c(m + n)\] \[a(m + n) \leq a \cdot m/2 + a \cdot n/2 + c(m + n)\] \[a(m/2 + n/2) \leq c(m + n)\]This holds for \(a \leq 2c\). Therefore \(T(m, n) = O(m + n) = O(m)\) since \(G\) is connected (\(m \geq n - 1\)). \(\square\)
Interactive: Borůvka MST Rounds
Each round, every component selects its lightest outgoing edge (green). These edges then join the MST (blue / bold) and the components merge. Nodes are coloured by component.
Summary & Comparison
| Algorithm | Problem | Time | Success Probability |
|---|---|---|---|
| Karger (single run) | Min-Cut | \(O(n^2)\) | \(\geq \dfrac{2}{n(n-1)} = \Omega(1/n^2)\) |
| Karger (repeated) | Min-Cut | \(O(n^4 \log(1/\varepsilon))\) | \(\geq 1 - \varepsilon\) |
| Karger-Stein (single run) | Min-Cut | \(O(n^2 \log n)\) | \(\Omega(1/\log n)\) |
| Karger-Stein (repeated) | Min-Cut | \(O(n^2 \log^2 n \cdot \log(1/\varepsilon))\) | \(\geq 1 - \varepsilon\) |
| Deterministic (max-flow) | Min-Cut | \(O(mn \log(n^2/m))\) | 1 (deterministic) |
| KKT | MST | \(O(m)\) expected | 1 (Las Vegas) |
Key Takeaways
- Karger’s algorithm is beautifully simple: just keep contracting random edges. The analysis reveals the \(\binom{n}{2}^{-1}\) bound via a telescoping product.
- Karger-Stein improves the success probability from \(\Omega(1/n^2)\) to \(\Omega(1/\log n)\) by branching when the contraction becomes risky, reducing total time from \(O(n^4)\) to \(O(n^2 \log^2 n)\).
- The counting result (at most \(\binom{n}{2}\) min-cuts) is a graph theory theorem that emerged purely from algorithm analysis.
- KKT achieves expected linear time for MST by combining Borůvka steps, random subsampling, and the subsampling lemma.
Tutorial Problems
Work through these problems to solidify your understanding of randomised graph algorithms.
Problem 1 Warm-up
How many distinct cuts does a graph on \(n\) vertices have? (A cut is a partition of \(V\) into two non-empty sets \((S, \bar{S})\), counted up to the symmetry \(S \leftrightarrow \bar{S}\).)
Each cut \((S, \bar{S})\) corresponds to a non-empty proper subset \(S \subseteq V\). There are \(2^n - 2\) such subsets (excluding \(\emptyset\) and \(V\)). Since \((S, \bar{S})\) and \((\bar{S}, S)\) are the same cut, the number of distinct cuts is:
\[\frac{2^n - 2}{2} = 2^{n-1} - 1\]\(\square\)
Problem 2 Warm-up
State the running time recurrence and the success probability recurrence for the Karger-Stein algorithm. Verify the claimed solutions:
(a) \(T(n) = O(n^2 \log n)\)
(b) \(p(n) = \Omega(1/\log n)\)
(a) Running time: \(T(n) = 2T(n/\sqrt{2}) + O(n^2)\). At depth \(j\) there are \(2^j\) subproblems of size \(n/(\sqrt{2})^j\). Work at depth \(j\): \(2^j \cdot O(n^2/2^j) = O(n^2)\). Depth: \(O(\log_{\sqrt{2}} n) = O(\log n)\). Total: \(O(n^2 \log n)\).
(b) Success probability: \(p(n) \geq 1 - (1 - p(n/\sqrt{2})/2)^2\). Setting \(\ell = \log_{\sqrt{2}}(n/6)\) (recursion depth), we get \(p(n) \geq 1/(\ell + 2) = \Omega(1/\log n)\) by Claim 27.1. \(\square\)
Problem 3 Warm-up
Consider modifying Karger-Stein so that instead of branching into 2 recursive calls, we make:
(a) Only 1 recursive call (no branching).
(b) 3 recursive calls.
What happens to the running time and success probability in each case?
(a) With 1 recursive call: \(T(n) = T(n/\sqrt{2}) + O(n^2) = O(n^2)\) (geometric series). The success probability satisfies \(p(n) \geq \frac{1}{2} \cdot p(n/\sqrt{2})\), so \(p(n) = \Omega(1/n^2)\) — no better than plain Karger. This is essentially the same as checking only every \(\sqrt{2}\) factor reduction, which doesn’t help.
(b) With 3 recursive calls: \(T(n) = 3T(n/\sqrt{2}) + O(n^2)\). At depth \(j\): \(3^j \cdot O(n^2/2^j)\). Since \(3/2 > 1\), this grows as \((3/2)^{\log n} = n^{\log_2 3} \approx n^{1.585}\). So \(T(n) = O(n^{2\log_2 3}) \approx O(n^{3.17})\). The success probability improves: \(p(n) \geq 1 - (1 - p(n/\sqrt{2})/2)^3\), which converges to a constant. So we get constant success probability but worse running time. \(\square\)
Problem 4 Problem Solving ⭐
Karger’s algorithm requires sampling an edge uniformly at random from the current multigraph. If the graph is stored as an adjacency list, sampling a uniform edge naively might take \(O(m)\) time. Describe how to sample a uniformly random edge in \(O(n)\) time.
Hint: Use a two-step process: first sample a vertex, then an incident edge.
Two-step sampling:
- Sample a vertex \(v\) with probability proportional to its degree: \(\Pr[v] = \deg(v) / (2|E|)\).
- Sample a uniformly random neighbour \(u\) of \(v\).
The probability of selecting edge \(e = \{u, v\}\) is:
\[\Pr[e] = \frac{\deg(u)}{2|E|} \cdot \frac{1}{\deg(u)} + \frac{\deg(v)}{2|E|} \cdot \frac{1}{\deg(v)} = \frac{1}{2|E|} + \frac{1}{2|E|} = \frac{1}{|E|}\]This is uniform! Step 1 requires a pre-computed prefix-sum array of degrees (can binary-search in \(O(\log n)\) time, or use an alias table for \(O(1)\)). Step 2 takes \(O(1)\) with adjacency-list random access. Overall: \(O(n)\) preprocessing per contraction step, \(O(1)\) per sample. \(\square\)
Problem 5 Problem Solving ⭐
A \(k\)-min-cut is a cut of size exactly \(k\) times the minimum cut value. Generalise Karger’s analysis:
(a) If we contract the graph down to \(2k\) vertices, what is the probability that a specific minimum cut survives?
(b) How many cuts of size at most \(k\) times the min-cut value can a graph on \(n\) vertices have?
(a) Contract to \(4k\) vertices (to leave a safety margin). Following the same telescoping product argument as Theorem 26, but with a cut of size \(\alpha k\) (where \(\alpha \leq k\) times the min-cut), at step \(i\) the graph has \(n - i + 1\) vertices and at least \((n - i + 1)k/2\) edges. The probability of hitting a specific cut of size \(\alpha k\) is \(\alpha k / |E_i| \leq 2\alpha / (n - i + 1)\). The survival probability through contracting to \(t\) vertices is:
\[\prod_{i=1}^{n-t} \left(1 - \frac{2\alpha}{n - i + 1}\right)\]For \(\alpha\)-approximate min-cuts: survival prob \(\geq \Omega(n^{-2\alpha})\).
(b) By the same argument as Theorem 29, the number of cuts of size at most \(\alpha k\) is at most \(O(n^{2\alpha})\). In particular, the number of \(\alpha\)-approximate min-cuts is polynomial in \(n\) for any fixed \(\alpha\). \(\square\)
Problem 6 Problem Solving ⭐
Assign each edge of a connected graph \(G = (V, E)\) a uniformly random weight from \([0, 1]\), independently. Let \(T\) be the MST under these random weights. Show that computing \(T\) via Kruskal’s algorithm is equivalent to Karger’s contraction algorithm. Deduce the running time.
Equivalence: Kruskal’s algorithm processes edges in increasing order of weight. With random weights from \([0,1]\), the edge ordering is a uniformly random permutation (with probability 1, all weights are distinct). At each step, Kruskal adds the lightest edge that connects two different components — equivalently, it contracts that edge.
Now consider Karger’s algorithm: at each step, it picks a uniformly random edge and contracts it. If we restrict to edges between different components (non-self-loops), picking a uniform random edge from the remaining inter-component edges is exactly the same as the next edge in a random permutation that connects two different components.
Therefore, Kruskal with random weights simulates Karger’s contraction: each “contraction” step picks a uniform random inter-component edge.
Running time: Kruskal’s algorithm sorts edges first, taking \(O(m \log m) = O(m \log n)\), then processes them with union-find in \(O(m \cdot \alpha(n))\). Total: \(O(m \log m)\). \(\square\)
Problem 7 Advanced ⭐⭐
Consider a weighted version of Karger’s algorithm: the graph has positive real edge weights, and the min-cut is the cut of minimum total weight. Instead of picking each edge with equal probability, we pick edge \(e\) with probability proportional to \(w(e)\). Show that the same \(\binom{n}{2}^{-1}\) success bound holds.
Let \(k\) be the minimum cut weight and let \(C\) be a specific min-cut of weight \(k\). The key observations:
- Min-degree bound: Every vertex has weighted degree at least \(k\) (otherwise the edges incident to that vertex would form a cut of weight \(< k\)). By the handshaking lemma: \(\sum_e w(e) \geq nk/2\).
- Probability of hitting \(C\): At step \(i\), the total edge weight is at least \((n-i+1)k/2\). The probability of sampling a \(C\)-edge is: \[\frac{\sum_{e \in C} w(e)}{\sum_{e \in E_i} w(e)} = \frac{k}{\sum_{e \in E_i} w(e)} \leq \frac{k}{(n-i+1)k/2} = \frac{2}{n-i+1}\]
This is exactly the same bound as in the unweighted case! The rest of the proof (telescoping product) goes through identically, yielding:
\[\Pr[\text{output} = C] \geq \frac{2}{n(n-1)} = \binom{n}{2}^{-1}\]\(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).