posted 18 Jan 2024

Minimum Cut

Notes Randomized Algorithms Minimum Cut

§ Overview

Suppose we are given graph GG with vertex set VV and edge set E.E.

Let V=[n],V = [n], then each edge e∈Ee \in E can be written as e=(u,v)e = (u, v) for u,v∈[n].u, v \in [n].

Cut

A cut C=S1,S2C = S_1, S_2 of graph GG is a partition of vertices VV into a set S1S_1 and S2=V∖S1.S_2 = V \setminus S_1.

An edge (u,v)(u, v) crosses the cut CC if u∈Siu \in S_i and v∈Sjv \in S_j for i≠j.i \neq j.

The size of the cut CC is the number of edges that cross C.C.

Minimum Cut

The minimum cut is the smallest cut across all pairs of sets of verticies.

§ Karger's Algorithm

Karger's Minimum Cut Algorithm

  1. Start with GG and iteratively reduce the number of vertices via edge contractions
  2. In each step, choose a random edge and merge the two endpoints of an edge into a single vertex which preserves edges.
    • Allow multi-edges but not self loops
  3. Iterate until there are only two vertices u1u_1 and u2u_2 left
  4. Return all vertices merged into u1u_1 as S1S_1, and the rest in u2u_2 as S2.S_2.

§ Analysis

Suppose the graph is disconnected. Then, we always return the correct min-cut.

Suppose the graph contains two components connected by a single edge. The algorithm is successful as long as it avoids selecting the single edge crossing the two components.

As long as it avoids the single edge, each edge contraction will shrink one of the two components.

It is unlikely that we choose that edge.

Fix a cut C=S1,S2C = S_1, S_2 of size k.k. The probability that we contract an edge of CC is k∣E∣.\frac{k}{|E|}. Since the min-cut is k,k, then each vertex must have degree of at least kk so ∣E∣≥nk2|E| \geq \frac{nk}{2} The probability that we do not contract an edge of CC is at least 1−knk/2=n−2n.1 - \frac{k}{nk/2} = \frac{n-2}{n}.

After ii steps, the number of vertices left is n−i;n-i; the probability that we do not contract an edge of CC is at least n−i−2n−i.\frac{n - i - 2}{n - i}.

The probability of success is at least

n−2n×n−3n−1×n−4n−2×⋯×13≥2n(n−1).\frac{n-2}{n} \times \frac{n-3}{n-1} \times \frac{n-4}{n-2} \times \cdots \times \frac{1}{3} \geq \frac{2}{n(n-1)}.

Therefore, the probability of success is at least 2n2,\frac{2}{n^2}, and after O(n2)\mathcal{O}\left(n^2\right) applications we will succeed with probability 0.99.0.99.