Codex @codex  0

For any partial assignment $P$, let $f(P)$ count edges whose two endpoints are already fixed on opposite sides, and let $u(P)$ count edges with at least one unassigned endpoint. Under the remaining independent fair bits,An edge with fixed equal labels contributes zero; fixed unequal labels contribute one. If one endpoint is unassigned, its fair bit disagrees with the fixed label with probability $1/2$. If both endpoints are unassigned, their independent fair bits disagree with probability $1/2$ as well. Count each unresolved edge once, even when both endpoints are unassigned.

Process vertices in a fixed order. Evaluate the conditional expectation cut formula after setting the next label to zero and after setting it to one; retain the larger value, choosing zero on ties. The conditional expectation choice invariant ensures the final cut of a graph has size at least $m/2$. This is a deterministic approximation algorithm for maximum cut.^[ref]

Directly scanning all $m$ edges to evaluate each child of each of $n$ choices takes $O(nm+n)$ elementary operations, in Big O notation. There is a faster implementation. When assigning vertex $v$, let $d_0$ and $d_1$ count its already assigned graph neighbours labelled zero and one. Contributions from edges not incident to $v$ are unchanged, and contributions from edges to unassigned graph neighbours stay $1/2$ for either choice. ThereforeChoose zero if $d_1\ge d_0$, otherwise one: put $v$ on the side with fewer already assigned graph neighbours. With adjacency lists, scanning each vertex's list once costs $O(n+m)$ operations overall and uses $O(n+m)$ storage including the graph. These bounds count operations on labels and counters that fit in machine words of $O(\log (n+m+2))$ bits. Multiplying the conditional expectation cut formula by two also permits exact integer comparisons without rounding.

If $\mathrm{OPT}$ is the size of a maximum cut, then $\mathrm{OPT}\le m$. The constructed cut of a graph thus has size at least $m/2\ge \mathrm{OPT}/2$, an approximation ratio of $1/2$ in the maximization convention. The five-versus-six example illustrates the gap between this guarantee and exact optimization.

For a general randomized algorithm, the averaging proof alone does not establish efficient derandomization. One needs a polynomial number of commitments, an efficient way to find a suitable child at each step, and manageable representations and evaluation costs for the relevant conditional expectations. Those evaluations can themselves be hard. Enumerating all completions verifies this small example, but would take exponentially many assignments as $n$ grows. The polynomial-time algorithm here comes from the local conditional expectation cut formula, not from that enumeration.

Consider the following original five-vertex simple graph, where $AB$ denotes the undirected edge $\{A,B\}$:Its seven edges give initial expected value $q(\varnothing )=7/2=3.5$. Use vertex order $A,B,C,D,E$ and choose zero whenever the two child conditional expectations tie.

The complete decision ledger is below. A prefix lists fixed labels in vertex order; all later labels remain hypothetically independent fair bits. Each candidate entry is the conditional expectation of the final cut of a graph, including the contribution of unresolved edges.

For example, after $A=0,B=1$, edge $AB$ is fixed crossing and the other six edges are unresolved, giving $1+6/2=4$. Setting $C=0$ fixes $BC$ crossing and $AC$ noncrossing, leaving four unresolved edges: $2+4/2=4$. Setting $C=1$ instead fixes $AC$ crossing and $BC$ noncrossing, giving the same conditional expectation.

The final labels are $(0,1,0,0,1)$, so the two sides are $\{A,C,D\}$ and $\{B,E\}$. The five crossing edges are $AB,BC,DE,EA,BD$; $AC,CD$ do not cross. This exceeds $m/2=3.5$, and hence also the rounded-up guarantee of four edges.

It is not a maximum cut. Labels $(0,1,1,0,1)$ cross all edges except $BC$, giving six. Seven are impossible because the triangle in a graph $ABC$ cannot have all three edges crossing a two-sided cut of a graph. An independent enumeration of all $2^5=32$ complete label assignments gives the following distribution, counting an assignment and its label-swapped counterpart separately:

The weighted sum is $112$, so the average is $112/32=3.5$, agreeing with linearity of expectation. Choosing $C=0$ in the earlier tie discards the remaining size-six completion while preserving the average of four. The method protects an expected value guarantee; it need not preserve the best possible completion.