Single-Vertex Flip Maximum Cut Local Search Algorithm

Definition

Single-Vertex Flip Maximum Cut Local Search Algorithm

For the unweighted Maximum Cut problem, start with any bipartition and repeatedly move a vertex to the opposite side whenever this strictly increases the cut size. Stop when no improving move exists.
The algorithm terminates in polynomial time and returns a cut of size at least $|E|/2\ge \mathrm{OPT}/2$.

What a flip changes

Compare same-side and crossing neighbours

For the current partition, let $s(v)$ count neighbours on the same side as $v$, and $c(v)$ count neighbours on the opposite side. Moving $v$ converts its $s(v)$ same-side edges into cut edges and its $c(v)$ cut edges into same-side edges. No nonincident edge changes.
$\text{new cut size}-\text{old cut size}=s(v)-c(v).$

A move improves the cut exactly when $s(v)>c(v)$. Equal counts do not justify a move: strict improvement is what guarantees termination.

Pseudocode

choose any bipartition A,B of V
repeat:
    compute s(v),c(v) for every vertex
    if no vertex satisfies s(v) > c(v):
        return A,B
    choose a vertex with s(v) > c(v)
    move it to the opposite side

Termination and running time

Each accepted move raises the integer cut size by at least one. The cut size lies between zero and $m=|E|$, so there are at most $m$ moves. Computing all neighbour counts and finding a move takes $O(n+m)$ time per scan. Including the final unsuccessful scan gives $O((m+1)(n+m))$ time and $O(n+m)$ space.

This argument uses unweighted edges. With arbitrary binary-encoded integer weights, a bound by the total weight would not by itself prove polynomial running time in the input length.

Approximation guarantee

Local optimality gives a global half-bound

Write the stopping condition at each vertex

At termination, no vertex has $s(v)>c(v)$, so $c(v)\ge s(v)$ for every $v$. Summing preserves the inequality:
${\sum }_{v\in V}c(v)\ge {\sum }_{v\in V}s(v).$

Count each edge at its two endpoints

Put $q=|\mathrm{CUT}(A,B)|$. Each crossing edge contributes one to $c$ at each endpoint, while each noncrossing edge contributes one to $s$ at each endpoint.

Therefore
${\sum }_{v}c(v)=2q,{\sum }_{v}s(v)=2(m-q).$
Substitution yields $2q\ge 2(m-q)$, hence $4q\ge 2m$ and finally $q\ge m/2$.

Compare with the optimum

No cut can contain more than all $m$ edges. Thus $\mathrm{OPT}\le m$, and
$q\ge \frac{m}{2}\ge \frac{\mathrm{OPT}}{2}.$

The algorithm need not find a globally maximum cut. Its stopping condition is enough to certify that at least half of all edges cross the returned partition.