Examples: 2-approximation for Max Cut; Turán’s theorem
Example: Max Cut
Given a graph G=(V,E) with m 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 v independently, color v red with probability 1/2; otherwise color v 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 G=(V,E) is a subset S of vertices such that no edge has both endpoints in S. Turán’s theorem is as follows:
Any graph G with n nodes and average degree \bar d has an independent set S of size at least n/(\bar d+1).
This bound is tight: consider the graph formed by the union of n/(\bar d + 1) cliques, each of size \bar d + 1. Every vertex has degree \bar d and every independent set has size at most n/(\bar d + 1).
To prove the theorem, consider the following random experiment:
Consider the vertices in random order. When considering a vertex v, add it to the set S if none of v’s neighbors have yet been added. Return S.
A vertex v with d_ v neighbors has a 1/(d_ v+1) chance of being considered first among its neighbors, in which case v will definitely be added. Hence, by linearity of expectation, the expected size of S is therefore at least \sum _{v\in V} {1}/{(d_ v+1)}. As a function of the d_ v’s, this quantity is minimized for fixed \sum _ v d_ v when each d_ v = \bar d. Thus, there exists an independent set S of size at least n/(\bar d+1).
