Prove a Half-Approximation for Max-Cut

Analyze vertex-flip local search and prove termination and a one-half guarantee.

Problem

Starting from any cut $(S,V\setminus S)$ in an unweighted graph, repeatedly move a vertex when doing so strictly increases the number of crossing edges. Prove polynomial termination under a suitable implementation and show that every local optimum has value at least $\mathrm{OPT}/2$ (indeed at least $|E|/2$).

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

At local optimality, each vertex has at least as many incident edges crossing as staying.

Hint 2

Sum this inequality over all vertices.

Hint 3

Each improving move increases an integer potential by at least one.

Full solution

Let $C$ be the set of crossing edges and $I=E\setminus C$. For a vertex $v$, write $c(v)$ and $i(v)$ for its incident crossing and noncrossing edges. Flipping $v$ changes the cut value by $i(v)-c(v)$, because precisely those two categories exchange roles. Therefore at a local optimum no vertex has $i(v)>c(v)$, so $c(v)\ge i(v)$ for every $v$.

Summing over vertices counts each edge twice:

Thus $|C|\ge|I|$, and since $|E|=|C|+|I|$, we get $|C|\ge |E|/2$. Every cut, including an optimal one, uses at most all edges, so $\mathrm{OPT}\le|E|$ and

This is a $1/2$-approximation under the maximization convention that the algorithmic value is at least $\rho\mathrm{OPT}$.

Termination alone follows because the cut value is an integer between zero and $|E|$ and each accepted move raises it by at least one. Hence there are at most $|E|$ moves. A simple implementation scans all vertices, computes $c(v),i(v)$ from adjacency lists, performs one improving flip, and repeats. Even recomputing from scratch gives polynomial time, for example $O(|V||E|^2)$ under a very naive scan; maintaining gains reduces this substantially. The approximation proof does not depend on the starting cut.

The strict-improvement rule matters. Allowing zero-gain flips without a tie-breaking potential can cycle. Weighted nonnegative integer edges admit the same local inequality and approximation guarantee, but a bound by total numeric weight is only pseudopolynomial in binary encoding; polynomial-time termination then needs a stronger implementation or scaling argument. The stated unweighted problem avoids that issue.

The guarantee may be loose for a particular graph, but it is logically valid because the stronger lower bound is against $|E|$. The proof does not assert that every local optimum is globally optimal.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Counting each edge once in one sum and twice in the other.
• Using $\mathrm{OPT}\ge|E|$ instead of $\mathrm{OPT}\le|E|$.
• Allowing zero-improvement moves and still claiming termination.

Sources and verification

• Merged summary, pp. 61-63
• Papadimitriou, ch. 13
• Corpus coverage note: No 2026 approximation transcript covers this exercise.
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.