Spectral Sparsification — Graph Cut Approximation

Spielman-Srivastava (2011): every graph has a sparse ε-spectral sparsifier with O(n log n / ε²) edges. Sample edges with probability proportional to effective resistance. Sparsifier preserves all cuts.

Graph Setup

N nodes: 30 Edge density p: 0.20 Sparsification ε: 0.30 Sample budget k×n: 3

Metrics

Original edges—

Sparse edges—

Compression—

λ₂ (orig)—

λ₂ (sparse)—

Cut approx ε—

Eff. resistance R_uv = (e_u - e_v)^T L⁺ (e_u - e_v)
Sample prob ∝ w_e × R_e

Guarantee: (1-ε)L ≼ L̃ ≼ (1+ε)L for all cuts.