\documentclass[12pt]{6042}
\usepackage{psfig}
\def\cut{\mbox{Cut}}

\begin{document}

\handout{maxcut}{The Maximum Cut Problem}{June 8, 1998}

We illustrate the application of Chebyshev's Theorem in the analysis of a
randomized algorithm for the Maximum Cut problem.

\section {The Problem}

Suppose $G = (V,E)$ is an undirected simple graph and $S \subseteq V$ is a
subset of the vertices.  So $S$ and its complement $V-S$ partition the
vertices into two parts.  An edge $e \in E$ is said to \emph{cross} the
partition iff one of the endpoints of $e$ is in $S$ and the other is in
$V-S$.  We also say that the partition {\em cuts} the edge when the edge
crosses the partition.  For any $S \subseteq V$, let $\cut_G(S)$ be the
number of edges that cross the partition $(S,V-S)$.

The \emph{Maximum Cut Problem} is, given $G$, to partition the vertices to
maximize the number of edges that cross the partition, that is, to find
$S$ such that $\cut_G(S)$ is a maximum.

A simple way of optimally solving Max Cut is to cycle through all the
possible partitions and then return the best one.  Unfortunately, this
exhaustive algorithm is impractical even for fairly small graphs because
the time it takes grows exponentially: it requires examination of
$2^{\card{V}}$ partitions.  There are good theoretical grounds to believe
that there is no significantly better optimal algorithm, i.e., that every
optimal algorithm for Max Cut must have a running time growing
exponentially in the number of vertices, at least in the worst case.
However, if we settle for \emph{approximately}, but not exactly, optimal
cuts, it is possible to find efficient algorithms which cut a lot of
edges.  In the next section we describe a simple-minded, efficient
randomized algorithm which does this.

\section {The Algorithm}

Consider the following randomized algorithm for the Maximum Cut problem:
initially let $S$ be empty; independently for each vertex $v \in V$ flip a
coin, and add $v$ to $S$ when the coin shows heads. 

This algorithm may not seem to make much sense.  First of all the
algorithm {\em does not even look at the graph}, but just makes random and
independent choices for each vertex.  So each of the subsets of $V$ is
equally likely to be chosen as $S$.  This means the worst possible
partition, namely $(\emptyset,V)$, is as likely to be generated as any
other partition.  Despite these objections, we will see that this simple
randomized algorithm has very good typical behavior.

\section{Some Random Variables}
Define for every vertex $v \in V$ a
Bernoulli random variable $X_v$ defined as follows:
\[ X_v = \left\{ \begin {array}{ll} 1 & \mbox{if } v \in S,\\
0 & \mbox{otherwise.}\end {array} \right. \]
The $X_v$s are mutually independent and unbiased by the definition of our
algorithm.

We also introduce a random variable $Y_{e}$ for every edge $e \in E$,
defined as follows:
\[ Y_e ::= \left\{ \begin {array}{ll} 1 & \mbox{if } e \mbox{ crosses }  (S,V-S),\\
0 & \mbox{otherwise.}\end {array}\right. \]
Notice that
\[\cut_G(S) = \sum_{e \in E} Y_{e} .\]

\begin {lemma}\label{unbiased}
The random variables $Y_e$ are unbiased.
\end {lemma}

\begin {proof}
We use the definition of crossing and the independence of the $X_v$s.
Let $\{ u,v\} \in E$, then

\begin {eqnarray*}
 \pr{ Y_{\{u,v\}} =1} &=& \pr {(X_u =1 \wedge X_v=0)
\vee (X_u=0 \wedge X_v=1)}\\
& =& \pr {X_u =1 \wedge X_v=0}
+ \pr { X_u=0 \wedge X_v=1}\\
& =&  \pr {X_u =1}\pr {X_v=0}+ \pr { X_u=0}\pr{ X_v=1}\\
& = & \frac 12 \frac 12 + \frac 12 \frac 12 \ =\ \frac 12 .
\end {eqnarray*}
\end {proof}

\begin {lemma}\label{pairwise}
The variables $Y_e$ are pairwise independent.
\end{lemma}

\begin {proof}
Consider two edges $e_1$ and $e_2$ in $E$. If the two edges 
do not share any vertex, then the independence of $Y_{e_1}$ and $Y_{e_2}$
follows from the independence of their endpoints.

The case to consider is when they share an endpoint, namely
$e_1 = \{u,v\}$ and $e_2 = \{ v,w\}$. Then, for example,
\begin {eqnarray*}
\pr { Y_{e_1} = 1 \wedge Y_{e_2} =1}
&=& \pr { X_u \neq X_v \wedge X_v \neq X_w}\\
&=& \pr{(X_u=X_w=0 \wedge X_v = 1) \vee (X_u=X_w=1 \wedge X_v = 0)}\\
&=& \pr{X_u=X_w=0 \wedge X_v = 1} + \pr{X_u=X_w=1 \wedge X_v = 0}\\
& = & \frac 18 + \frac 18\ =\ \frac 14\\
& = &  \pr { Y_{e_1} = 1} \pr{ Y_{e_2} =1},
\end {eqnarray*}
and similar calculations work for every other value of $Y_{e_1}$
and $Y_{e_2}$.
\end {proof}

\section{The Analysis}

By Lemma~\ref{unbiased}, $\expect{Y_e} = 1/2$.  Using the linearity of
expectation, we conclude that
\[
\expect{\cut_G(S)}  =  \expect {\sum_{e \in E} Y_{e}} = \sum_{e \in E}
\expect{Y_e} =  \card{E}/2.
\]
In other words, our algorithm cuts on the average half the edges.  (It is
an interesting corollary of this calculation that in every graph there
{\em always exists} a vertex partition that cuts at least half the edges.)

The next step of our analysis consists in bounding the probability that
our algorithm performs much worse than its expected behavior.

By Lemma~\ref{pairwise}, the random variable $\cut_G(S)$ is a sum of
pairwise independent unbiased Bernoulli variables, and so
\[ \variance{\cut_G(S)} = \variance{\sum_{e \in E} Y_{e}} =
\card{E}\variance{Y_e} = \frac {\card{E}}{4} . \]

Using the Chebyshev bound, we can now estimate the probability that the
number of cut edges differs much from $\card{E}/2$.  Namely, for every
constant $c>0$,
\[ \pr{\abs{\cut_G(S) - {\card{E}/2}} \geq c \sqrt{\card{E}}} \leq
\frac{1}{4c^2} . \]
For example, there is less than a $0.1 \%$ chance that the number of cut
edges deviates from the expectation by more than an additive term $8
\sqrt{\card{E}}$---a very small term compared to $\card{E}$ when there are
a lot of edges.

Since our goal is to maximize the number of cut edges, we can
use the stronger estimate given by the one-sided Chebyshev
Theorem,
\[ \pr{ \cut_G (S) \leq \card{E}/2 -  c\sqrt{\card{E}}} \leq \frac{1}{1 + 4c^2} .\]

We remark that although the variables $Y_e$ are pairwise independent, they
are not even three-way independent.  For example, if edges $e_1,e_2,e_3$
form a triangle, then $(Y_{e_1} + Y_{e_2}) \bmod 2 = Y_{e_3}$, so the values
of any two of the variables $Y_{e_1}, Y_{e_2}, Y_{e_3}$ uniquely
determine the value of the third.  That's why the Chernoff bound, which
requires full independence, is not applicable.


\section{How Close to Optimal?}

Since the random algorithm above produces a partition that cuts at least
half the edges, it will, with high probability, inevitably cut at least
$50\%$ of the number of edges which can optimally be cut.  This is the
best percentage of optimal that can be guaranteed for this algorithm.  For
example, on a bipartite graph with an equal number of vertices in each
half, the algorithm will cut on the average half of the edges, whereas
partitioning into the two halves of the bipartite graph cuts \emph{all}
the edges.

The algorithm above does come close to optimal with very high probability
on cliques, that is, graphs with edges between every two vertices.
Namely, for a clique with $2n$ vertices, the best partition divides the
vertices into two blocks of $n$, so that $n^2$ of the $n(2n-1)$ edges are
cut.  Our randomized algorithm cuts on the average $n(2n-1)/2 = n^2 - n/2$
edges, and cuts with high probability $n^2 - O(n)$ edges.  So in this case
the algorithm can be expected to cut nearly 100\% of the optimal number of
edges as $n$ increases.

An algorithm essentially equivalent to the random one above was proposed
in 1974.  Despite much effort, no efficient algorithm guaranteeing a
better ratio to the optimum had been found until 1994, when Goemans and
Williamson at MIT found an efficient algorithm for cutting at least
$87.8\%$ of the optimum number of edges.  This percentage is the best
which has been achieved to date.  It is also known that finding cuts
within a factor $16/17 \approx 94.1\%$ of the optimum is as hard as
solving the problem optimally, so there is not much room for improvement
on the Goemans and Williamson percentage.

These notes are by Luca Trevisan.

\end{document}
