Examples: 2-approximation for Max Cut; Turán’s theorem
Example: Max Cut
Given a graph with edges, the Max Cut problem is to color each vertex red or blue so as to maximize the number of edges with differently colored endpoints. (Say such an edge is “cut”.) The problem is NP-hard.
Consider the following random experiment: For each vertex independently, color red with probability ; otherwise color blue.
The probability that any given edge is cut is 1/2. Thus, by linearity of expectation, in expectation half the edges are cut. Thus, by the existence principle above, there exists a coloring that cuts at least half the edges. Since no coloring can cut more than twice this many edges, such a coloring is a 2-approximate solution.
This example apparently appeared first in a 1965 paper of Erdős [1, Lemma 1].
Example: Turán’s theorem
Here is a slightly more sophisticated example. An independent set in a graph is a subset of vertices such that no edge has both endpoints in . Turán’s theorem is as follows:
Any graph with nodes and average degree has an independent set of size at least .
This bound is tight: consider the graph formed by the union of cliques, each of size . Every vertex has degree and every independent set has size at most .
To prove the theorem, consider the following random experiment:
Consider the vertices in random order. When considering a vertex , add it to the set if none of ’s neighbors have yet been added. Return .
A vertex with neighbors has a chance of being considered first among its neighbors, in which case will definitely be added. Hence, by linearity of expectation, the expected size of is therefore at least As a function of the ’s, this quantity is minimized for fixed when each . Thus, there exists an independent set of size at least .