# Johnson-Cut Max-Cut Approximation

The Johnson-Cut is an $O(n^2)$ Max-Cut approximation with a factor of 2. I have these definitions for MC and none for JC so I assume they're the same:

$G = (V,E,w)$ with $|V| = n$ and $w : E \rightarrow Q^+$

Maximize $w(V_1,V_2) = \sum_ {v_1 \in V_1, v_2 \in V_2} w(v_1,v_2)$

The algorithm is

JohnsonCut(G = (V,E,w))
V1,V2 := ∅;
for v ∈ V do
if w(v,V1) > w(v,V2) do
V2 := V2 ∪ {v}
else
V1 := V1 ∪ {v}
fi
od
return (V1,V2)


My intuition tells me this means that $MC/2 \leq JC \leq MC$ (rather than $JC \leq 2MC$) but the proof eludes me. It is evident that the algorithm isn't performing anywhere near enough comparisons for optimality but why is it performing enough to guarantee a factor of 2?

-
You'd better explain what $w$ is. I thought at first that $w(u,v)$ would be the capacity of the edge between $u$ and $v$, but no, its first argument is a vertex and its second argument is a set of vertices, so that's not it. Is $w(v, S)$ the sum of the capacities of all the edges $(u,v)$ for $u\in S$? – MJD May 20 '12 at 5:35
There; and that is how I understand it, though I'm not really much of an authority on the matter. – Quail May 20 '12 at 6:37

OK, so if $w(v,V_x) = \sum_ {v \notin V_1 \cup V_2, v_x \in V_x} w(v,v_x)$ we can look at what the cut for each iteration will yield.

The first vertex we look at will of course be added to $V_1$, both $V_1$ and $V_2$ are empty sets, so $w(v,V_x)$ will return 0 in both calls.

Note that we only look at each edge once (if an edge goes to neither set, we don't bother with it yet). This is the key to it all.

$v$ is the vertex we are examining in the current iteration.
Name the sum of the weight of all edges of $v$ that go to $V_1$ $w_{v_1}$ and all that go to $V_2$ $w_{v_2}$. $z$ is the cut we are going to choose and $w_z$ its weight.

Clearly $w_z \geq (w_{v_1} + w_{v_2})/2$ (hint: set $z=v_1$, times 2 minus $w_{v_1}$).

The sum of all our cuts would then be: $\sum{w_z} \geq \frac{\sum{w_{v_1}+ w_{v_2}}}{2}$

The sum of the weight of all the edges in the graph is $W$. The Max-Cut result can of course not be greater than that.
Because we are only looking at each edge exactly once we know that $W=\sum{w_{v_1} + w_{v_2}}$.
Ergo $\sum{w_z} \geq \frac{W}{2}$

The running time should be $O(n^2)$. We look at $n$ vertices, but each of them can have edges to $n - 1$ other vertices.

-