Random contraction and random hyperplanes · Lecture 24 · November 13, 2026
CS 574 · University of Illinois, Urbana-Champaign
Partition the vertices into two nonempty sets.
How few edges can cross? How many can cross?
| Topic | Random choice | Minutes |
|---|---|---|
| Minimum cut | Contract a random edge | 25 |
| Faster minimum cut | Branch before contraction gets risky | 15 |
| Maximum cut | Round vectors with a random hyperplane | 25 |
| Why the relaxation is convex | Use a Gram matrix | 10 |
Min cut: preserve one optimal solution.
Max cut: preserve a fraction of the relaxed objective in expectation.
For \(G=(V,E)\), write \(n=|V|\) and \(m=|E|\).
For \(\varnothing\ne S\subsetneq V\), define
\[\delta(S)=\{uv\in E:u\in S,\ v\notin S\}.\]
The cut size is \(|\delta(S)|\).
\(S\) and \(V\setminus S\) describe the same cut.
We begin with a connected graph; a disconnected graph has min cut \(0\).
\[S=\{a,b,c\},\qquad |\delta(S)|=1.\]
The bridge \(cd\) is a minimum cut.
\[S=\{a,c,e\},\qquad |\delta(S)|=5.\]
Each triangle contributes at most two edges; the bridge contributes at most one.
How few edges can cross a cut? How many can cross?
\[S=\{1,\ldots,15\},\qquad |\delta(S)|=2.\]
Splitting either wheel cuts at least three edges. Separating the wheels cuts only two.
\[|\delta(S)|=2(14+7)+2=44\quad\text{out of 58 edges}.\]
Each wheel contributes at most \(21\) crossing edges; both joining edges also cross.
Choose an edge \(uv\) and merge its endpoints into one supervertex.
Delete self-loops. Keep parallel edges.
Each supervertex remembers the original vertices it contains.
Stop when two supervertices remain: they define a cut of the original graph.
Contract \(ab\). The target cut keeps \(a\) and \(b\) together anyway.
The two edges represent the original edges \(ac\) and \(bc\).
Sample uniformly among edge copies, including multiplicities.
Contract one of the two edges between \(ab\) and \(c\).
Both copies become self-loops and disappear. The bridge survives.
The target cut still has one crossing edge.
\[\{a,b,c\}\ \mid\ \{d,e,f\}.\]
Count the remaining edge copies: the returned cut has size \(1\).
No later cut can put \(c\) and \(d\) on opposite sides.
The original bridge cut has been lost.
Contracting \(cd\), then \(ab\), then \(ef\), then \(ab\) with \(cd\) can return
\[\{a,b,c,d\}\mid\{e,f\},\qquad |\delta(S)|=2.\]
Every original vertex inherits the side of its supervertex.
Every cut of a contracted graph lifts to a cut of the original graph, with the same size.
Contraction can remove candidate cuts. It cannot create a smaller cut.
Fix one minimum cut \(C\). If no contracted edge belongs to \(C\), then \(C\) survives.
We never need to know which edges belong to a minimum cut.
\[|\delta(\{c\})|=\deg(c)=3.\]
A minimum cut can be no larger than this candidate cut.
Let the minimum cut have size \(k\).
Every vertex has degree at least \(k\), because isolating it gives a cut.
Therefore
\[2m=\sum_{v\in V}\deg(v)\geq nk,\qquad m\geq\frac{nk}{2}.\]
Only \(k\) of these edge copies belong to the fixed cut \(C\).
\[\Pr[\text{choose }uv]=\frac{\mu_{uv}}{\sum_e\mu_e},\qquad \sum_e\mu_e=2+1+1+1+1=6.\]
Choose the blue edge with probability \(2/6\); hit the red cut edge with probability \(1/6\).
Condition on \(C\) surviving until \(r\) supervertices remain.
The current graph still has minimum cut \(k\), so
\[\Pr[\text{contract an edge of }C\mid C\text{ survives}] =\frac{k}{m_r}\leq\frac{2}{r}.\]
The chance of a safe next step is at least \(1-2/r\).
These are guarantees, not the exact survival probabilities of our example graph.
\[\begin{aligned} \Pr[C\text{ survives to two vertices}] &\geq\prod_{r=3}^{n}\left(1-\frac2r\right)\\ &=\frac{n-2}{n}\frac{n-3}{n-1}\cdots\frac13\\ &=\boxed{\frac{2}{n(n-1)}}. \end{aligned}\]
The contraction events are dependent. The chain rule is enough.
Let \(p=2/[n(n-1)]\) and run \(R\) independent trials.
\[\Pr[\text{all trials fail}]\leq(1-p)^R\leq e^{-pR}.\]
For \(R=n(n-1)\), failure is at most \(e^{-2}<0.14\).
Keeping the smallest returned cut is safe: no trial can return less than optimum.
The horizontal axis counts independent trials, not contractions within a trial.
With a multiplicity representation, one contraction takes \(O(n)\) time.
One trial: \(O(n^2)\).
Constant success probability: \(O(n^4)\).
High probability: \(O(n^4\log n)\).
The notes also give a random-weight MST interpretation.
\[\Pr[C\text{ survives down to }r]\geq\frac{r(r-1)}{n(n-1)}.\]
Read the curve from right to left as contraction proceeds.
Share the cheap, safer progress. Spend repetitions near the risky end.
If \(n\leq6\), enumerate all cuts and return a minimum cut.
Otherwise set \(t=\lceil1+n/\sqrt2\rceil\).
Independently contract two copies of \(G\) to \(t\) vertices.
Recursively solve both smaller graphs; return the smaller lifted cut.
The two branches use independent random choices.
The two recursive branches begin from independently contracted graphs of this size.
\[\Pr[C\text{ survives to }t]\geq\frac{t(t-1)}{n(n-1)}\geq\frac12,\]
where \(t=\lceil1+n/\sqrt2\rceil\).
The \(+1\) and ceiling make the finite-\(n\) inequality valid.
One surviving branch is enough, provided its recursive call succeeds.
In a complete binary tree of height \(h\), independently retain each edge with probability \(1/2\).
Let \(\rho_h\) be the probability of a retained root-to-leaf path; \(\rho_0=1\).
\[\rho_1=3/4.\]
\[\rho_h=1-\left(1-\frac{\rho_{h-1}}2\right)^2 =\rho_{h-1}-\frac{\rho_{h-1}^2}{4}.\]
For height one, \(\rho_1=1-(1/2)^2=3/4\).
The picture suggests the inequality; the next slide proves it for every depth.
\[\boxed{\rho_h\geq\frac1{h+1}}.\]
For \(f(x)=x-x^2/4\), \(f\) is increasing on \([0,1]\).
If \(\rho_{h-1}\geq1/h\), then
\[\rho_h\geq\frac1h-\frac1{4h^2}\geq\frac1{h+1}.\]
The final inequality is equivalent to \(3h\geq1\); the base case is \(h=0\).
Let \(p_h\) be a uniform success lower bound for calls with at most \(h\) levels left.
Each branch succeeds with probability at least \(p_{h-1}/2\).
Conditional on the input graph, the two branches are independent, so
\[p_h\geq1-(1-p_{h-1}/2)^2\geq\rho_h.\]
Depth \(h=O(\log n)\) gives success probability \(\Omega(1/\log n)\).
At level \(\ell\), there are \(2^\ell\) calls, each on about \(n/\sqrt{2^\ell}\) vertices.
Ignoring bounded rounding terms,
\[T(n)=2T(n/\sqrt2)+O(n^2).\]
At level \(\ell\):
\[2^\ell\cdot O\!\left((n/\sqrt{2^\ell})^2\right)=O(n^2).\]
There are \(O(\log n)\) levels: one FastCut run costs \(O(n^2\log n)\).
One run succeeds with probability at least \(c/\log n\) for a constant \(c>0\).
After \(R=O(\log^2 n)\) independent runs,
\[\Pr[\text{failure}]\leq e^{-cR/\log n}\leq n^{-2}.\]
Total time: \(\boxed{O(n^2\log^3 n)}\).
Again, return the smallest cut found.
Why must parallel edges retain their multiplicities?
Why can the min cut never decrease under contraction?
Why is preserving one fixed minimum cut enough?
For each edge \(ij\), let \(\omega_{ij}\geq0\); set \(\omega_{ij}=0\) on nonedges.
\[\operatorname{OPT}=\max_{S\subseteq V}\; \sum_{i\in S,\ j\notin S}\omega_{ij}.\]
MAX CUT is NP-hard. We seek an approximation.
Nonnegative weights will be essential when summing edgewise inequalities.
\[w(\{3\},\{1,2\})=2+3=5.\]
Every cut of a triangle misses an edge; missing the lightest is optimal.
The expression \((1-y_i y_j)/2\) is exactly the crossing indicator.
Assign \(y_i=+1\) for \(i\in S\) and \(y_i=-1\) otherwise.
\[\frac{1-y_i y_j}{2}= \begin{cases} 0,&y_i=y_j,\\ 1,&y_i\ne y_j. \end{cases}\]
\[\operatorname{OPT}=\max_{y_i\in\{-1,+1\}} \frac12\sum_{i<j}\omega_{ij}(1-y_i y_j).\]
If \(y_1\ne y_2\) and \(y_2\ne y_3\), then \(y_1=y_3\).
The edge preferences are coupled by a single assignment to every vertex.
Allowing more directions keeps every discrete solution feasible.
Replace \(y_i\in\{-1,+1\}\) by a unit vector \(v_i\):
\[\gamma^*=\max_{\|v_i\|=1} \frac12\sum_{i<j}\omega_{ij}(1-\langle v_i,v_j\rangle).\]
A sign assignment is feasible: choose \(v_i=y_i e_1\).
Therefore \(\gamma^*\geq\operatorname{OPT}\).
Each pair has dot product \(-1/2\), hence contribution \((1+1/2)/2=3/4\).
The relaxed value is \(3\cdot3/4=9/4\), while \(\operatorname{OPT}=2\).
The boundary is the hyperplane \(H=\{x:\langle x,r\rangle=0\}\).
Both endpoints use the same random normal.
This picture shows a planar vector configuration. The algorithm also works in higher dimensions.
The cut is \(\{1\}\mid\{2,3\}\) and has weight \(2\).
Every nonboundary normal yields a \(1\)–\(2\) split of these three vectors.
Rounding returns weight \(2\); the relaxed value was \(9/4\).
The angle should determine the separation probability.
Let \(\theta_{ij}=\arccos\langle v_i,v_j\rangle\in[0,\pi]\).
\[\boxed{\Pr[ij\text{ crosses the rounded cut}]=\frac{\theta_{ij}}{\pi}}.\]
The relaxed contribution is \(\omega_{ij}(1-\cos\theta_{ij})/2\).
The expected rounded contribution is \(\omega_{ij}\theta_{ij}/\pi\).
\[\langle v_i,r\rangle=\langle v_i,r_g\rangle, \qquad\langle v_j,r\rangle=\langle v_j,r_g\rangle.\]
Only the projection of \(r\) onto \(\operatorname{span}\{v_i,v_j\}\) affects the two dot products.
Rotational symmetry makes the projected direction uniform on the circle.
The signs change on the lines perpendicular to \(v_i\) and \(v_j\).
Equal vectors are never separated; opposite vectors are always separated.
Two sectors of angle \(\theta\) give probability \(2\theta/(2\pi)\).
For \(\theta=\pi/3\), the separation probability is \(1/3\).
For \(\theta=\pi/2\), both the separation probability and the relaxed edge value are \(1/2\).
For \(\theta=2\pi/3\), separation probability is \(2/3\); relaxed edge value is \(3/4\).
We need a single \(\alpha\) such that
\[\frac{\theta}{\pi}\geq\alpha\frac{1-\cos\theta}{2} \qquad(0\leq\theta\leq\pi).\]
\[\alpha=\min_{0<\theta\leq\pi} \frac{2\theta}{\pi(1-\cos\theta)}\approx0.878567.\]
The minimum occurs near \(\theta=2.331122\) radians.
| Angle | Rounded probability | Relaxed edge value | Ratio |
|---|---|---|---|
| \(\pi/3\) | \(1/3\) | \(1/4\) | \(4/3\) |
| \(\pi/2\) | \(1/2\) | \(1/2\) | \(1\) |
| \(2\pi/3\) | \(2/3\) | \(3/4\) | \(8/9\) |
| \(\pi\) | \(1\) | \(1\) | \(1\) |
Some edges gain; some lose. Every edge retains at least an \(\alpha\) fraction in expectation.
The expected total is \(2\), even though all three edge indicators use the same hyperplane.
Let \(W\) be the rounded cut weight, and \(\gamma\) the feasible vector objective.
\[\begin{aligned} \mathbb E[W] &=\sum_{i<j}\omega_{ij}\frac{\theta_{ij}}\pi\\ &\geq\alpha\sum_{i<j}\omega_{ij}\frac{1-\cos\theta_{ij}}2\\ &=\alpha\gamma. \end{aligned}\]
Linearity of expectation does not require different edges to be independent.
For an optimal vector solution,
\[\mathbb E[W]\geq\alpha\gamma^*\geq\alpha\operatorname{OPT}, \qquad\alpha>0.87856.\]
This is an expected approximation guarantee.
A particular random hyperplane can return a worse cut.
Here \(\operatorname{OPT}=4\). A single rounding can fall below \(\alpha\operatorname{OPT}\).
The source’s optimization machinery computes an arbitrarily close approximation.
If a feasible solution has \(\gamma\geq\gamma^*-\eta\), then
\[\mathbb E[W]\geq\alpha(\gamma^*-\eta) \geq\alpha\operatorname{OPT}-\alpha\eta.\]
The ideal ratio follows as the solver tolerance tends to zero.
The matrix stores all pairwise inner products of one common vector configuration.
Collect the vectors into the columns of \(V\) and define their Gram matrix
\[M=V^\mathsf{T}V,\qquad M_{ij}=\langle v_i,v_j\rangle.\]
Unit vectors give \(M_{ii}=1\).
For every \(z\in\mathbb R^n\),
\[z^\mathsf{T}Mz=\|Vz\|^2\geq0.\]
A real symmetric matrix \(M\) is positive semidefinite, written \(M\succeq0\), if
\[z^\mathsf{T}Mz\geq0\qquad\text{for every }z.\]
Conversely, \(M\succeq0\) admits a factorization \(M=B^\mathsf{T}B\).
If \(M_{ii}=1\), the columns of \(B\) are unit vectors ready for rounding.
\[M=\begin{pmatrix} 1&-1/2&-1/2\\ -1/2&1&-1/2\\ -1/2&-1/2&1 \end{pmatrix}.\]
The diagonal entries are one. The eigenvalues are \(0,3/2,3/2\).
This matrix is positive semidefinite, even though it is singular.
It represents the three vectors spaced \(120^\circ\) apart.
So three unit vectors cannot have all three pairwise dot products equal to \(-1\).
An apparent solution would set every off-diagonal entry to \(-1\):
\[A=\begin{pmatrix}1&-1&-1\\-1&1&-1\\-1&-1&1\end{pmatrix}, \qquad \mathbf1^\mathsf{T}A\mathbf1=-3<0.\]
It is not positive semidefinite, so no unit-vector configuration realizes it.
The PSD constraint enforces consistency among all pairwise dot products.
\[\begin{aligned} \text{maximize}\quad &\frac12\sum_{i<j}\omega_{ij}(1-M_{ij})\\ \text{subject to}\quad &M_{ii}=1\quad(i=1,\ldots,n),\\ &M\succeq0. \end{aligned}\]
The objective is linear in \(M\); the feasible region is convex.
The integrality restriction has become a matrix constraint.
\[M(x)\succeq0\quad\Longleftrightarrow\quad -1\leq x\leq1.\]
Let \(A,B\succeq0\) and \(0\leq t\leq1\).
For every vector \(z\),
\[z^\mathsf{T}(tA+(1-t)B)z =t\,z^\mathsf{T}Az+(1-t)z^\mathsf{T}Bz\geq0.\]
Thus \(tA+(1-t)B\succeq0\).
The constraints \(M_{ii}=1\) also survive convex combinations.
Optimization supplies the correlations. Randomness turns them into a partition.
Why is the relaxed optimum an upper bound on MAX CUT?
Why does an angle \(\theta\) give separation probability \(\theta/\pi\)?
Where do we use nonnegative weights?
| Min cut | Max cut | |
|---|---|---|
| Random operation | Contract an edge copy | Choose a hyperplane normal |
| Object tracked | One fixed optimum | Each edge’s contribution |
| Main calculation | Conditional survival product | Angle divided by \(\pi\) |
| Output guarantee | Exact, with high probability | \(\alpha\) approximation in expectation |
Contraction preserves a discrete witness.
Rounding converts continuous structure into a discrete solution.
Notes 17 — Min Cut: contraction, amplification, and recursive branching.
Notes 46 — Approximate Max Cut: vector relaxation, angular rounding, and semidefinite programming.
Exercises from the min-cut notes: implement the MST interpretation; reduce FastCut’s space to \(O(n^2)\).
For the triangle, verify the relaxed optimum \(9/4\) and the rounded value \(2\).
CS 574 · Lecture 24 · Min Cut and Max Cut