Motivation
A local-search algorithm starts with a feasible solution and makes a small change whenever that change improves the objective. The final solution may not be globally optimal, but the absence of any permitted improvement can itself imply a useful approximation guarantee. Maximum cut gives a particularly clear example: when no vertex benefits from moving to the other side, at least half of the total edge weight is cut.
The proof of quality and the proof that the algorithm terminates are separate. With arbitrary nonnegative real weights, a strict-improvement rule terminates because there are finitely many cuts, but that observation does not provide a polynomial bound in the input length. With integral weights, each improvement is at least one, giving a bound in the numerical total weight.
Definitions
Definition 1.1.1
(Cut value)
Let be a finite undirected loopless graph with nonnegative edge weights . Parallel edges are allowed and are counted separately. A cut is a partition of into two sides. Its value is the sum of weights of edges with endpoints on opposite sides. Let , and let be the largest cut value. Since weights are nonnegative, .
Definition 1.1.2
(Vertex gain and one-vertex local optimality)
For a vertex in a cut, write for the total weight of incident cut edges and for the total weight of incident uncut edges. Moving alone to the other side changes the cut value by . A cut is one-vertex locally optimal if no single move strictly increases its value, equivalently for every vertex.
Theorems
Theorem 1.1.3
(Quality of a local optimum)
Every one-vertex locally optimal cut in a finite loopless graph with nonnegative weights has value at least , and hence at least .
Theorem 1.1.4
(Termination of strict improvement)
Starting from any cut, repeatedly moving a vertex with terminates at a one-vertex locally optimal cut. If all edge weights are nonnegative integers, there are at most moves. This numeric bound alone need not be polynomial in the binary input length.
Proof sketch or proof idea
Proof
(Double counting, then termination by strict improvement)
At a local optimum, sum over all vertices. Every cut edge is counted at both endpoints on the left, and every uncut edge is counted at both endpoints on the right. Thus and . Since no cut can weigh more than , . The loopless assumption ensures that moving a vertex changes the status of every incident edge; a loop would always remain uncut and would invalidate the stated move formula unless handled separately.
Each strict-improvement move increases the objective. There are only finitely many assignments of vertices to sides, so a cut cannot be revisited and the process terminates. At termination no vertex has positive gain, which is exactly the local-optimality condition. With integer weights, every positive gain is an integer at least one. The objective starts nonnegative and never exceeds , so there are at most moves. A number written in binary can be exponentially larger than its representation length, which is why this is a numerical rather than a polynomial-time guarantee.
Proof X-ray
Double counting supplies the guarantee
The local inequalities are per vertex. Summing them counts each edge twice, once at each endpoint; this turns many local statements into one global comparison between cut and uncut weight.
Worked examples
Worked example 1.1.5
(A triangle)
Give each edge of a triangle weight one. A cut with one vertex on one side and two on the other has value two. The singleton has cut weight two and uncut weight zero; either other vertex has cut and uncut incident weight one each. No single move strictly improves the cut. The optimum is two, since a triangle cannot cut all three edges.
Worked example 1.1.6
(A strict improvement)
For a path with unit weights, start with all vertices on one side. The cut value is zero. Moving changes both edges from uncut to cut, increasing the value by two. The resulting cut has value two, which equals the total weight and is optimal.
Worked example 1.1.7
(A locally optimal cut need not be globally optimal)
For a four-cycle with unit edges, put two adjacent vertices on each side. Two opposite boundary edges are cut, so ; each vertex has one cut and one uncut incident edge, and every single move has zero gain. This is a local optimum under the strict-improvement definition. Alternating the sides cuts all four edges, giving value four. The ratio shows the theorem's factor is tight for arbitrary one-vertex local optima.
Common mistakes
Counterexample mode
No improving single move does not mean global optimum
The four-cycle cut above cannot be improved by moving one vertex, yet moving to an alternating partition doubles its value. Local optimality is always relative to the allowed neighborhood.
Common mistake
(Zero-gain moves can cycle)
Allowing zero-gain moves without an anti-cycling rule can revisit a cut forever. The termination proof uses strict improvement. Also, the statement relies on nonnegative weights when it is converted into an approximation of ; negative-weight variants require separate definitions and analysis.
Reading the local inequalities
The condition says that at least half of the total weight incident to each vertex is already crossing the cut. It is not a statement that every individual incident edge is cut. In the four-cycle example each vertex has one cut and one uncut edge, so equality is possible at every vertex while the global cut is only half of the optimum.
The double-counting identity can be written explicitly:
Every loopless edge contributes its weight at both endpoints and belongs to exactly one of the two classes. Summing the local inequalities yields . The argument applies to disconnected graphs and isolated vertices as well. An isolated vertex has and its side has no effect on the objective.
Worked example 1.1.8
(Weighted local check)
Take a path with edge weights and . In the cut , the cut value is . At , ; at it is ; at it is . The last vertex has positive gain , so this cut is not locally optimal. Moving gives , cuts both edges, and has value .
Strict improvement and running time
An implementation can scan the vertices, find one with positive gain, move it, and repeat. At every step the current assignment is a valid cut. After a move, the gains of the moved vertex and its neighbors can change; gains of non-neighbors do not. An implementation maintaining gains must update them consistently and must examine all vertices before declaring local optimality. A full scan provides a direct certificate: report each pair and check .
The finite-state termination argument applies to arbitrary real weights, including irrational ones, because a strict increase prevents a return to any earlier cut. There are at most assignments of vertices to two labeled sides. This is an exponential upper bound on the number of distinct assignments, not a polynomial-time guarantee. Treating the two sides as interchangeable could reduce the number of distinct unlabeled cuts, but it does not change the conclusion about the need for a complexity analysis.
For integer weights the gain is an integer, so each strict move raises the cut value by at least one. If , every edge has weight zero, every cut is already locally optimal, and no move occurs. If , the number of moves is bounded by regardless of the rule for choosing an improving vertex. Since the bit length of is logarithmic in its numerical magnitude, this gives a pseudo-polynomial bound for the straightforward algorithm. A stronger polynomial-time result would require a different argument or algorithm and is not established here.
Approximation and edge cases
For a maximization problem, a approximation guarantee is . The ratio is meaningful when . If all weights are zero, the inequality still says , while the quotient is undefined. Stating the inequality directly handles this boundary case without inventing a numerical ratio.
The proof compares the local cut with , an upper bound that is easy to compute. It may be a weak bound: in a triangle of unit weights, but the optimum is two. The stronger observation that no cut of a triangle contains all three edges is special to that graph. The local-search proof needs no such structural analysis and applies to every graph under the stated assumptions.
A random cut independently assigns each vertex to a side and has expected value . That averaging argument proves existence of a cut at least as good as half the total, but a random realization can be worse. The local-search theorem instead certifies the quality of every terminal cut under its one-vertex rule. The two arguments share a bound and use different evidence: expectation in one case, the per-vertex inequalities in the other.
Common mistake
(Equality in the half bound does not certify optimality)
The four-cycle also shows why equality in the half bound cannot by itself establish optimality. In its adjacent-pair cut, both sides of the double-counting inequality are equal, but the optimum is twice the local value. Improving the approximation guarantee requires additional algorithmic ideas or a larger neighborhood, together with a new proof; the displayed theorem makes no such claim.
Checking a proposed terminal cut
A reader can verify a claimed local optimum without replaying the sequence of moves. List the two sides of the partition, compute the cut value, and for each vertex sum incident weights separately over neighbors on the same and opposite sides. If every opposite-side sum is at least the same-side sum, the cut is locally optimal. The double-counting proof then supplies the approximation inequality. If even one vertex violates the inequality, moving it gives an explicit strictly better cut and disproves the local-optimality claim.
This check also makes clear which data the guarantee depends on. The weights must be those of the instance being evaluated, and every edge must be counted with its stated multiplicity. Parallel edges contribute independently to the endpoint sums and to . The proof does not require a particular initial partition or a particular sequence of improving vertices, so different runs can end at different local optima while each still has the same half-total-weight guarantee.
A certificate of local optimality is weaker than a certificate of global optimality. To prove global optimality in the weighted path example, one also exhibits a cut of value , matching the universal upper bound. In the four-cycle example, the local inequalities are valid but a better cut disproves global optimality. Keeping those claims separate prevents the algorithm's stopping condition from being mistaken for a proof that no multi-vertex change can help.
Derandomizing the half-weight guarantee
The local-search proof uses inequalities at a terminal cut. There is another way to construct a half-weight cut: fix the vertices one at a time while preserving a conditional expectation. Start with a finite loopless undirected graph with nonnegative weights and total weight . Imagine assigning every vertex independently to or with probability . For each edge, its endpoints differ with probability , so the expected cut value is . This uses linearity of expectation; the edge indicators need not be independent.
After fixing some vertices, imagine that every remaining vertex is still assigned by an independent fair coin. Call the expected value of this hypothetical completion . A fully fixed crossing edge contributes its full weight to , a fully fixed same-side edge contributes zero, and an edge with at least one unfixed endpoint contributes half its weight. For the next vertex , let and be the two expectations after fixing it to or . The two possible coin outcomes are equally likely, so
At least one of is at least . Choose such a side, breaking ties either way, and repeat. Starting from the empty assignment gives a nondecreasing sequence beginning at . Once every vertex is fixed, there is no randomness left: is the value of the constructed cut. Thus . Nonnegative weights justify ; when the inequality is valid, although a ratio is undefined. This is a deterministic construction, not a claim that every random cut achieves the expected value.
Worked example 1.1.9
(A separate weighted triangle)
Consider a different triangle from the unit-weight example above: , , , so . Fix in that order and, for this trace, choose on a tie. Entries are exact conditional expectations, not simulated averages.
| Next vertex | Choice | Retained | ||
|---|---|---|---|---|
Initially . After and , edge is fixed crossing and contributes ; the two unresolved edges contribute , giving . Finally cuts but not , so the actual cut is . The guaranteed lower bound is ; the larger value here is a property of this instance and these choices, not a general guarantee.
The comparison must be made at every step to retain the proof from the start. If a student chooses a worse side manually, the remaining best-side choices still preserve the expectation of that new prefix, but the earlier loss need not be recovered. For example, fixing and then lowers to ; the best remaining choice yields . Finishing a manual prefix therefore does not retroactively certify the original half-weight bound.
For implementation, when deciding , only its edges to already fixed neighbors distinguish from : edges to unfixed neighbors contribute half under either choice. Sum the weights from to fixed neighbors on each side and choose the side opposite the larger sum. With adjacency lists this takes arithmetic operations over a full run, since each edge is inspected only at its endpoints. Bit complexity still depends on the input representation and exact arithmetic. This construction need not produce a one-vertex local optimum; its certificate is the maintained conditional expectation, not the local inequalities used earlier.
Summary
At a one-vertex local optimum every vertex has at least as much incident cut weight as uncut weight. Double counting gives a half-total-weight guarantee. Strict improvements terminate, while the numeric integral-weight bound must not be confused with a polynomial bit-complexity bound.
Exercises
Quick check
(In a unit-weight triangle, verify the local inequalities for the two-vertex side in the worked cut.)
Add up the cut and uncut incident weight at one vertex.
Solution · Answer
Each of the two vertices has one edge to the singleton and one edge to the other vertex on its own side. Thus .
Quick check
(What is the gain from moving the middle vertex of an uncut unit-weight path on three vertices?)
Compare the status of the two incident edges before and after the move.
Solution · Answer
Both incident edges become cut, so the gain is .
Quick check
(Why is the four-cycle example locally optimal even though it is not globally optimal?)
Compute the gain at one vertex, then compare with the alternating cut.
Solution · Answer
Each vertex has one cut and one uncut incident edge, so its gain is zero. The alternating cut has value four rather than two.
Quick check
(If integral weights sum to , what upper bound does the theorem give on the number of strict-improvement moves?)
Each strict move raises the integral cut value by at least one.
Solution · Answer
At most : the integral cut value increases by at least one per move and never exceeds the total weight.