1. Formal Invariant — Karger's Contraction Survival & Freivalds' Witness
Theorem 1: Karger's Contraction Survival Bound (1993)
Let $G = (V, E)$ be a connected undirected multigraph with $N$ vertices, and let $C^*$ be any specific global minimum cut of cardinality $k = |C^*|$. Since every vertex in $G$ has degree at least $k$, the total number of edges satisfies $|E| \ge \frac{N k}{2}$. Thus, the probability that the first random edge contraction hits $C^*$ is at most $\frac{k}{N k / 2} = \frac{2}{N}$. Conditioning across all $N - 2$ contractions down to 2 vertices, the probability that $C^*$ survives untouched is:
$$\Pr[C^* \text{ survives}] \ge \prod_{i=0}^{N-3} \left(1 - \frac{2}{N - i}\right) = \frac{N-2}{N} \cdot \frac{N-3}{N-1} \cdot \frac{N-4}{N-2} \cdots \frac{2}{4} \cdot \frac{1}{3} = \frac{2}{N(N-1)}$$
Theorem 2: Freivalds' $O(N^2)$ Matrix Product Verification (1977)
To verify whether $A \cdot B = C$ for $N \times N$ matrices without $O(N^3)$ multiplication, pick a random binary vector $r \in \{0, 1\}^N$ and check whether $A(Br) = Cr$ in $O(N^2)$ time! If $AB \ne C$, then $\Pr[A(Br) = Cr] \le \frac{1}{2}$ per trial ($\le 2^{-k}$ after $k$ trials).
2. Karger-Stein Recursive Amplification ($O(N^2 \log^3 N)$)
(Survival Prob >= 1/2!)"] Branch --> T2["G2 = Contract(G, down to t vertices)
(Independent Run, Prob >= 1/2!)"] T1 --> R1["c1 = FastCut(G1)"] T2 --> R2["c2 = FastCut(G2)"] R1 --> Min["Return min(c1, c2)"] R2 --> Min
Notice why **Karger-Stein (1996)** is a masterpiece of algorithm design: in Karger's product, the early contractions are very safe (probability $1 - 2/N$), whereas the late contractions when only a few vertices remain are dangerous. By contracting from $N$ down to $t = \lceil 1 + N / \sqrt{2} \rceil$ vertices, the survival probability is $\approx \frac{t(t-1)}{N(N-1)} \ge \frac{1}{2}$! Branching into **two independent recursive calls** at threshold $t$ satisfies $T(N) = 2 T(N / \sqrt{2}) + O(N^2) = O(N^2 \log N)$ per tree with success probability $\Omega(1 / \log N)$.
3. Converting Between Las Vegas and Monte Carlo
Markov's Inequality & Verification Oracles
- Monte Carlo $\to$ Las Vegas: If you have a Monte Carlo algorithm with success probability $p$ AND a fast deterministic checker that verifies correctness, repeating the Monte Carlo algorithm until the checker accepts yields a Las Vegas algorithm with expected $1/p$ runs.
- Las Vegas $\to$ Monte Carlo: If a Las Vegas algorithm has expected runtime $\mu$, aborting it after $k \cdot \mu$ steps and outputting a default answer yields a deterministic-time Monte Carlo algorithm that fails with probability $\le 1/k$ (by Markov's Inequality).
4. Complexity Matrix
Simulate Karger random multigraph edge contractions down to 2 supernodes, 3-SAT ≤_p Vertex Cover gadget graphs, and Knapsack FPTAS value-bucket scaling K = εP/n.
Invariant & State
| Algorithm | Class | Time Complexity | Error / Success Bound |
|---|---|---|---|
| Single Trial Karger Contraction (DSU) | Monte Carlo | O(M alpha(N)) | Success $\ge \frac{2}{N(N-1)}$ |
| Full Karger Min-Cut ($\binom{N}{2} \ln N$ trials) | Monte Carlo | O(N^2 M log N) | Error $\le 1 / N$ |
| Karger-Stein Recursive Min-Cut | Monte Carlo | O(N^2 log^3 N) | Error $\le 1 / N$ |
| Freivalds' Matrix Product Check ($k$ trials) | Monte Carlo | O(k * N^2) | One-sided error $\le 2^{-k}$ |
5. Production-Grade C++20 Implementation (Karger Contraction + Freivalds' Verifier)
#include <vector>
#include <cstdint>
#include <numeric>
#include <random>
#include <algorithm>
struct Edge { int u, v; };
// Single contraction trial of Karger's Algorithm using Disjoint Set Union (DSU)
int karger_single_trial(int n, std::vector<Edge> edges, std::mt19937_64& rng) {
std::shuffle(edges.begin(), edges.end(), rng);
std::vector<int> parent(n), sz(n, 1);
std::iota(parent.begin(), parent.end(), 0);
auto find = [&](auto& self, int x) -> int {
return parent[x] == x ? x : parent[x] = self(self, parent[x]);
};
int components = n;
for (const auto& e : edges) {
if (components <= 2) break;
int ru = find(find, e.u);
int rv = find(find, e.v);
if (ru != rv) {
if (sz[ru] < sz[rv]) std::swap(ru, rv);
parent[rv] = ru;
sz[ru] += sz[rv];
--components;
}
}
int cut_edges = 0;
for (const auto& e : edges) {
if (find(find, e.u) != find(find, e.v)) {
++cut_edges;
}
}
return cut_edges;
}
// Freivalds' O(k * N^2) Monte Carlo verification of A * B == C
bool freivalds_verify(const std::vector<std::vector<int64_t>>& A,
const std::vector<std::vector<int64_t>>& B,
const std::vector<std::vector<int64_t>>& C,
int trials = 40) {
const int n = static_cast<int>(A.size());
std::mt19937_64 rng(1337);
std::vector<int64_t> r(n), Br(n), ABr(n), Cr(n);
for (int t = 0; t < trials; ++t) {
for (int i = 0; i < n; ++i) r[i] = rng() & 1ULL;
// Compute Br = B * r in O(N^2)
for (int i = 0; i < n; ++i) {
int64_t s = 0;
for (int j = 0; j < n; ++j) if (r[j]) s += B[i][j];
Br[i] = s;
}
// Compute ABr = A * (Br) and Cr = C * r in O(N^2)
for (int i = 0; i < n; ++i) {
int64_t sab = 0, sc = 0;
for (int j = 0; j < n; ++j) {
sab += A[i][j] * Br[j];
if (r[j]) sc += C[i][j];
}
if (sab != sc) return false; // 100% certain witness that A * B != C
}
}
return true; // Probability of false positive <= 2^{-40}
}Production Pitfall — Picking Random Vertex Pairs Instead of Random Edges in Karger's Algorithm
If you implement Karger's algorithm by picking two uniformly random super-vertices $(u, v)$ to merge instead of a uniformly random remaining edge $e \in E$, the algorithm fails exponentially! Why? Consider two $K_n$ cliques joined by a single bridge edge: picking two random vertices almost always merges vertices inside the same clique, except when it picks one vertex from each clique and destroys the bridge with probability $1/2$. Picking a random edge biases selection proportionally to vertex degree, protecting sparse cuts!