Min Cut and Max Cut

Random contraction and random hyperplanes · Lecture 24 · November 13, 2026

Sariel Har-Peled

CS 574 · University of Illinois, Urbana-Champaign

One graph, two optimization problems

Two triangles connected by one edge.

Partition the vertices into two nonempty sets.

How few edges can cross? How many can cross?

Today’s route

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.

A cut is a partition

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\).

The smallest cut in our example

Blue vertices form S; thick red edges cross the cut.

\[S=\{a,b,c\},\qquad |\delta(S)|=1.\]

The bridge \(cd\) is a minimum cut.

The largest cut in the same graph

Blue vertices form S; five red edges cross.

\[S=\{a,c,e\},\qquad |\delta(S)|=5.\]

Each triangle contributes at most two edges; the bridge contributes at most one.

A larger graph: the same two questions

Two wheel graphs joined by two edges: 30 vertices and 58 edges.

How few edges can cross a cut? How many can cross?

A larger minimum cut: separate the clusters

Blue vertices form S; the two thick red joining edges cross the minimum cut.

\[S=\{1,\ldots,15\},\qquad |\delta(S)|=2.\]

Splitting either wheel cuts at least three edges. Separating the wheels cuts only two.

A larger maximum cut: alternate around each rim

Blue vertices form S; all rim edges, half the spokes, and both joining edges cross.

\[|\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.

Min cut: shrink the graph

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.

Choose an edge inside one side

The green edge ab is selected; the red bridge is the cut we want to preserve.

Contract \(ab\). The target cut keeps \(a\) and \(b\) together anyway.

Parallel edges are essential

After merging a and b, there are two edges between ab and c.

The two edges represent the original edges \(ac\) and \(bc\).

Sample uniformly among edge copies, including multiplicities.

Finish the left triangle

The supervertex abc contains the original left triangle.

Contract one of the two edges between \(ab\) and \(c\).

Both copies become self-loops and disappear. The bridge survives.

Shrink the right side

After contracting de, the two edges from de to f remain parallel.

The target cut still has one crossing edge.

Two supervertices give the answer

The final two supervertices recover the bridge cut.

\[\{a,b,c\}\ \mid\ \{d,e,f\}.\]

Count the remaining edge copies: the returned cut has size \(1\).

What if we contract the bridge?

The merged supervertex cd straddles the original minimum cut.

No later cut can put \(c\) and \(d\) on opposite sides.

The original bridge cut has been lost.

A valid answer can still be suboptimal

This original-graph partition has two crossing edges.

Contracting \(cd\), then \(ab\), then \(ef\), then \(ab\) with \(cd\) can return

\[\{a,b,c,d\}\mid\{e,f\},\qquad |\delta(S)|=2.\]

Lift a cut back to the original vertices

The two parallel edges on the left lift to de and df on the right. The cut has size two in both graphs.

Every original vertex inherits the side of its supervertex.

What contraction preserves

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.

Karger’s random contraction algorithm

  1. Start with one supervertex per original vertex.
  2. While more than two remain, choose a uniformly random edge copy and contract it.
  3. Delete self-loops and retain all other edge copies.
  4. Return the cut defined by the final two supervertices.

We never need to know which edges belong to a minimum cut.

A vertex’s incident edges form a cut

Isolating c cuts precisely its three incident edges ac, bc, and cd.

\[|\delta(\{c\})|=\deg(c)=3.\]

A minimum cut can be no larger than this candidate cut.

A small cut forces many safe edges

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\).

Tickets: one edge record with its multiplicity

Each distinct edge appears once. Edge labels and box widths encode its multiplicity; the blue record represents ac and bc.

\[\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\).

The next contraction is unlikely to hit C

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\).

Survive one contraction at a time

For n=6, bar widths show the survival lower bounds after successive safe contractions; arrows give the conditional lower-bound factors.

These are guarantees, not the exact survival probabilities of our example graph.

Multiply conditional probabilities

\[\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.

Several trials, one retained candidate

Four possible returned cuts have sizes 2, 2, 2, and 1. Keep the green-framed candidate of size 1.

Repeat and keep the smallest cut

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.

Repetition drives the failure bound down

For n=6, one-trial success is at least 1/15. The dashed all-fail bound lies below the blue exponential bound; 30 trials give at most e to the minus 2.

The horizontal axis counts independent trials, not contractions within a trial.

Cost of the basic algorithm

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.

The risky steps come late

Survival lower bound versus remaining vertices r, with n=100.

\[\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.

Branch before the graph gets too small

Two independently contracted children, followed by recursive branching.

Share the cheap, safer progress. Spend repetitions near the risky end.

Karger–Stein: FastCut

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.

Stop while survival is still likely

For n=100, the prescribed threshold is t=72. The red point is above 1/2; contracting all the way to r=2 gives a much smaller bound.

The two recursive branches begin from independently contracted graphs of this size.

Each branch preserves C with probability at least 1/2

\[\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.

A binary-tree survival experiment

The blue path illustrates one surviving route to a leaf.

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\).

Height one: three ways to survive

The four equally likely outcomes. Solid blue edges are retained; dashed edges are absent. Only the first outcome has no retained path.

\[\rho_1=3/4.\]

The branching recurrence

Each branch succeeds with probability rho at the child times 1/2 for its first edge.

\[\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\).

What the induction needs to show

The blue values follow the exact branching recurrence. The red curve is the lower bound 1/(h+1).

The picture suggests the inequality; the next slide proves it for every depth.

Survival is at least inverse 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\).

Apply the comparison to FastCut

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)\).

Twice as many calls, half the work per call

Each rectangle represents one call’s quadratic work. Ignoring rounding, every row has total area proportional to n squared.

At level \(\ell\), there are \(2^\ell\) calls, each on about \(n/\sqrt{2^\ell}\) vertices.

Work at each recursion level

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)\).

Amplify the faster algorithm

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.

Check the min-cut proof

Why must parallel edges retain their multiplicities?

Why can the min cut never decrease under contraction?

Why is preserving one fixed minimum cut enough?

Switch objectives: maximize the crossing weight

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.

A weighted example

The cut isolating vertex 3 crosses the edges of weights 2 and 3.

\[w(\{3\},\{1,2\})=2+3=5.\]

Every cut of a triangle misses an edge; missing the lightest is optimal.

One edge, four sign assignments

Equal signs leave the edge uncut; opposite signs cut it. Blue vertices have sign +1.

The expression \((1-y_i y_j)/2\) is exactly the crossing indicator.

Encode the cut by signs

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).\]

A triangle cannot satisfy every edge

The three nontrivial cuts of an unweighted triangle each cross two edges.

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.

A sign solution already lives on a sphere

The cut isolating vertex 1 becomes two antipodal unit vectors; vertices 2 and 3 share the negative vector.

Allowing more directions keeps every discrete solution feasible.

Relax signs to unit vectors

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

Vectors can spread around a triangle

Three unit vectors separated by 120 degrees.

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\).

Round with a random hyperplane

  1. Compute a nearly optimal feasible vector solution.
  2. Choose a uniform random unit normal \(r\).
  3. Set \(S=\{i:\langle v_i,r\rangle\geq0\}\).

The boundary is the hyperplane \(H=\{x:\langle x,r\rangle=0\}\).

Both endpoints use the same random normal.

A concrete hyperplane cut

Green H separates blue vectors with positive dot product from red vectors with negative dot product.

This picture shows a planar vector configuration. The algorithm also works in higher dimensions.

Round the triangle

This normal puts v1 on one side and v2,v3 on the other.

The cut is \(\{1\}\mid\{2,3\}\) and has weight \(2\).

Rotate the normal

Another normal isolates v2 instead.

Every nonboundary normal yields a \(1\)–\(2\) split of these three vectors.

Rounding returns weight \(2\); the relaxed value was \(9/4\).

Equal, perpendicular, or opposite?

Three vector configurations with representative dashed hyperplanes. Equal vectors stay together; opposite vectors split; orthogonal vectors split half the time.

The angle should determine the separation probability.

Analyze one edge at a time

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\).

Project the normal into the relevant plane

Oblique view of a 3D configuration: the dashed perpendicular drops \(r\) to its orthogonal projection \(r_g\) in the blue plane \(g\).

\[\langle v_i,r\rangle=\langle v_i,r_g\rangle, \qquad\langle v_j,r\rangle=\langle v_j,r_g\rangle.\]

Why a planar picture proves the formula

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.

A 60-degree angle

Red sectors are the normal directions that separate the blue vectors; dashed lines are perpendicular to them.

Two sectors of angle \(\theta\) give probability \(2\theta/(2\pi)\).

For \(\theta=\pi/3\), the separation probability is \(1/3\).

A right angle

The separating sectors cover half the circle of normal directions.

For \(\theta=\pi/2\), both the separation probability and the relaxed edge value are \(1/2\).

A 120-degree angle

The separating normal directions cover two thirds of the circle.

For \(\theta=2\pi/3\), separation probability is \(2/3\); relaxed edge value is \(3/4\).

Two functions to compare

Red: separation probability. Blue: relaxed contribution for an edge of weight one.

We need a single \(\alpha\) such that

\[\frac{\theta}{\pi}\geq\alpha\frac{1-\cos\theta}{2} \qquad(0\leq\theta\leq\pi).\]

The worst edgewise ratio

The ratio curve, shown for theta at least 0.8 radians; it diverges as theta approaches zero.

\[\alpha=\min_{0<\theta\leq\pi} \frac{2\theta}{\pi(1-\cos\theta)}\approx0.878567.\]

The minimum occurs near \(\theta=2.331122\) radians.

Some edgewise ratios

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.

Add the contributions edge by edge

For the 120-degree triangle, the top row adds three relaxed contributions; the bottom row adds three expected rounded contributions, on the same scale.

The expected total is \(2\), even though all three edge indicators use the same hyperplane.

Sum the edgewise guarantee

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.

The Goemans–Williamson guarantee

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.

One vector solution can give different cut values

Two roundings of the same optimal tetrahedral vector solution for the complete graph on four vertices: a singleton cut of weight 3 and a balanced cut of weight 4.

Here \(\operatorname{OPT}=4\). A single rounding can fall below \(\alpha\operatorname{OPT}\).

Solvers use finite precision

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.

Read dot products into a matrix

The red 120-degree angle gives the two red entries \(M_{12}=M_{21}=-1/2\). Each diagonal entry records a unit vector’s squared length.

The matrix stores all pairwise inner products of one common vector configuration.

Where is the convex optimization problem?

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.\]

Positive semidefinite means a Gram representation

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.

The triangle’s Gram matrix

\[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.

Pairwise wishes must agree globally

If both v1 and v3 point opposite to v2, they must point in the same direction as each other.

So three unit vectors cannot have all three pairwise dot products equal to \(-1\).

Why not make every pair opposite?

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.

The semidefinite program

\[\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.

A concrete segment of feasible Gram matrices

For \(M(x)\) with diagonal entries \(1\) and off-diagonal entries \(x\), every point of the red segment is feasible. The midpoint matrix has orthogonal vector columns.

\[M(x)\succeq0\quad\Longleftrightarrow\quad -1\leq x\leq1.\]

Why the PSD region is convex

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.

From the solver back to a cut

The triangle goes from a graph to its Gram matrix, to vectors and a hyperplane, and finally to a cut with two crossing edges.

Optimization supplies the correlations. Randomness turns them into a partition.

Check the max-cut proof

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?

Two roles for randomness

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.

Reading and follow-up

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\).