Nagamochi-Ibaraki Algorithm

Purpose: Compute a global minimum cut deterministically in $O(nm+n^2\log n)$ without any max-flow computation, and — separately — build sparse $k$-connectivity certificates in $O(m)$.

Two contributions

1. Minimum cut by maximum adjacency ordering

This is the algorithm usually presented as Stoer-Wagner; Nagamochi and Ibaraki published the underlying idea first (1992), and Stoer and Wagner gave the simplified presentation (1997).

The core lemma: build a maximum adjacency (MA) ordering $v_1,v_2,\dots ,v_n$, where each next vertex is the one most strongly connected to the already-chosen set. Then the cut separating the last vertex $v_n$ from everything else is a minimum $v_{n-1}$-$v_n$ cut. Merge $v_{n-1}$ and $v_n$ and repeat $n-1$ times, keeping the best cut seen.

2. Sparse certificates — the more useful idea

A $k$-connectivity certificate of $G$ is a subgraph $H$ with $O(kn)$ edges such that every cut of size $<k$ in $G$ is preserved exactly in $H$.

Construction (scan-first search): repeatedly extract a spanning forest $F_1$ of $G$, then a spanning forest $F_2$ of $G\setminus F_1$, and so on $k$ times. The union $F_1\cup \cdots \cup F_k$ is a certificate with at most $k(n-1)$ edges, and the whole thing can be built in $O(m)$ time with a single scan-first search.

Why certificates matter

They let you replace $m$ with $kn$ in any algorithm that only cares about cuts of size $\le k$:

• $k$-edge-connectivity testing — sparsify first, then run the expensive algorithm on $O(kn)$ edges
• Min cut — if you only need to know whether the min cut is below $k$
• Max flow with small value — sparsify to $O(kn)$ edges when the flow is known to be $\le k$
• Dynamic connectivity — certificates are maintained incrementally to keep the edge count low

This is a very general “sparsify before you compute” pattern, and the same philosophy later produced cut sparsifiers (Benczúr-Karger) and spectral sparsifiers (Spielman-Teng), which preserve all cuts approximately with $\tilde{O}(n/{\epsilon }^2)$ edges.

Complexity

Task	Time
MA ordering (one phase)	$O(m+n\log n)$ with a heap
Global min cut ($n-1$ phases)	$O(nm+n^2\log n)$
$k$-certificate via scan-first search	$O(m)$

Variants / Use Cases

• Stoer-Wagner — the cleaner presentation of the min-cut half; write this one
• Karger-Stein — the randomized competitor
• Global Min Cut — the topic page
• Benczúr-Karger cut sparsification — approximate certificates with $\tilde{O}(n/{\epsilon }^2)$ edges preserving all cuts within $1\pm \epsilon$
• Dynamic connectivity — sparse certificates keep the maintained structure small