Minimum Cuts in Graphs — revisiting my 1998 ETH semester thesis

Thomas Kausch · October 2026

In 1998 I wrote my semester thesis at ETH Zürich on one of graph theory’s classic questions: how do you split a network into two parts while cutting as little as possible? Supervised by Prof. Emo Welzl and Joachim Giesen, it covers why many cut problems are NP-complete, a simple flow-free algorithm that solves the minimum cut anyway, and a small trick that makes it faster in practice. Read the full thesis (PDF, German)

The problem

A minimum cut splits the nodes of a weighted network into two non-empty groups so that the total weight of the edges between them is as small as possible. It is the network’s weakest point: the cheapest place where it falls apart.

The question shows up in network reliability, circuit design and transport planning. The surprise is how fragile its tractability is. Ask for the maximum cut, or a cut into two equal halves, and the problem becomes NP-complete. Allow negative edge weights and even the minimum cut is NP-complete. Yet with positive weights, the minimum cut is solvable in polynomial time.

What the thesis covers

Six chapters, 43 pages, written in German and submitted on 3 February 1998 – this was my birthday.

Chapter	Question	Result
1. Complexity	How hard are cut problems in general?	Max-Cut, Max-Bisection and Min-Bisection are NP-complete (via reductions from NAESAT)
2. A simple min-cut algorithm	Can we find a minimum cut without flow computations?	Yes: the Stoer–Wagner algorithm, O(|V||E| + |V|² log |V|), with a short correctness proof
3. Improved algorithm	Can phases be cut short?	Merge two nodes early when that cannot lose the minimum cut; same worst case, faster in practice
4. Upper bounds	How large can a minimum cut be?	min degree ≤ 2|E|/|V|; locally minimal cuts ≤ |E|/2; a ½-approximation for Max-Cut
5. Minimum s-t cuts	How many distinct s-t cut values exist?	At most |V| − 1; every graph is cut-equivalent to a tree; |V| − 1 s-t computations are necessary and sufficient
6. Max-flow and min-cut	Why does flow equal cut?	A self-contained proof of the Ford–Fulkerson max-flow min-cut theorem

The core idea

The Stoer–Wagner algorithm (1994) finds a minimum cut with no flow computations at all, in |V| − 1 nearly identical phases. Each phase works like this:

1. Start with any node in a growing set A.
2. Repeatedly add the node most strongly connected to A.
3. The last node added, t, gives a candidate cut: t versus everything else.
4. Remember that cut, then merge t with the second-to-last node s.

The smallest candidate over all phases is the minimum cut. The proof fits on a page, and a priority queue makes it run in O(|V||E| + |V|² log |V|).

My improvement: stop a phase early. As soon as the next node’s connection weight to A reaches the best cut found so far, the s-t cut in that phase cannot beat it, so s and t can be merged right away. Seeding the algorithm with a cheap first guess — the node with the smallest degree, found in O(|V| + |E|) — lets this kick in from phase one.

The worst case stays the same, and the thesis proves exactly when: on a cycle with equal weights, every s-t cut weighs the same, so no phase can ever stop early.

Upper bounds: a good first guess

The better the starting guess, the more phases end early, so chapter 4 asks how large a minimum cut can be in a multigraph.

Bound	Method	Takeaway
Minimum cut ≤ smallest node degree	Direct construction: cut one node off	Cheap and usually tight, but fails badly on two dense clusters joined by one edge
Minimum cut ≤ 2|E|/|V|	Random cut analysis, then a simpler deterministic proof	Always weaker than the degree bound
Locally minimal cut ≤ |E|/2	Local-search argument	A minimum cut is either locally minimal or trivial; the same reasoning yields a ½-approximation for Max-Cut in O(|E|²)

Why it still matters

The same question — where is a network weakest? — sits under network resilience, clustering and image segmentation today. Three lessons from the thesis carry over to everyday engineering:

• Small changes flip hardness. Min-cut is easy, max-cut is NP-complete. Knowing which side of that line your problem sits on saves months.
• Simple beats clever. Stoer–Wagner matched the best known bounds with an algorithm you can implement in an afternoon and prove on a page.
• A good guess pays twice. A cheap upper bound turns a worst-case algorithm into a fast one on real inputs.

Algorithms #GraphTheory #ETHZurich #ComputerScience #SoftwareEngineering