Max-Cut

Given a graph $G = (V, E)$, partition the vertex set into two sets $(A, B)$. An edge is said to be cut by this partition, if its end points lie on different sides of the partition. Find a partition that maximizes the number of edges cut (see figure ).

Figure: Finding a max-cut.

This problem is NP-hard. We will give a simple 0.5-approximation algorithm for this problem through randomization. This was the best known approximation guarantee for this problem for several years.

Let $\vert V\vert = n$ and $\vert E\vert = m$.

Claim 1. There exists a partition $(A, V \setminus A)$ of the vertex set such that number of edges cut $\geq \frac{\vert E\vert}{2} = \frac{m}{2}$.

Proof: We build a set $A$ (i.e., one side of the partition) by including each vertex in $A$ with probability 0.5. Now we ask the question: what is the expected number of edges cut by the partition $(A, V \setminus A)$. To answer this question, for every edge $(i, j)\in E$, we define $X_{ij} = 1$ if the edge $(i, j)$ is cut by the partition, 0 otherwise.

We can write the following expression for the number of edges cut $(X)$:

$$X = \sum_{(i,j)\in E} X_{ij}$$ (8.7)

The question we want to answer is: $E[X]=?$ We use the linearity of the expectations. First convince your self that $E[X_{ij}] = \frac{1}{2}$.

This holds since, conditioned on $i$ being in the set $A$ or not, there is exactly one choice for $j$, which makes the edge $(i, j)$ a cut. Hence, we get the following:

$$E[X] = \sum_{(i,j)\in E}E[X_{ij}] = \frac{m}{2}.$$ (8.8)