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 .

What a flip changes

Compare same-side and crossing neighbours

For the current partition, let count neighbours on the same side as , and count neighbours on the opposite side. Moving converts its same-side edges into cut edges and its cut edges into same-side edges. No nonincident edge changes.

A move improves the cut exactly when . 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 , so there are at most moves. Computing all neighbour counts and finding a move takes time per scan. Including the final unsuccessful scan gives time and 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 , so for every . Summing preserves the inequality:

Count each edge at its two endpoints

Put . Each crossing edge contributes one to at each endpoint, while each noncrossing edge contributes one to at each endpoint.

Therefore

Substitution yields , hence and finally .

Compare with the optimum

No cut can contain more than all edges. Thus , and

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.