1. An times polylog-approximation for coloring -colorable graphs
1. Reduce degree as before.
2. Recall the SDP relaxation we used on wednesday. Minimize under constraints , . Today, we merely change the rounding procedure.
3. Rounding. Let be well-chosen values, . While max degree , pick a random Gaussian vector . Consider the affine (i.e. does not go through the origin) hyperplane normal to defined by . It isolates a part of the vertices,
which need not form an independant set. So take
color in one color and remove it.
4. Color remainder with colors.
Analysis. Since the Gaussian density is rotation invariant and a tensor product of one variable Gaussians,
Since , where is unit and orthogonal to . So , where the normal Gaussian random variable is independant from . So the conditional probability
where is the maximum degree. Choose so that . We shall use the rough estimates, for
The upper bound gives
Using the lower bound, we get
where is the current number of vertices (remember that we keep discarding vertices once colored). Markov inequality applied to gives
If this happens, we do nothing. Else, we remove , and decreases at least by a factor .
How many colors have been used ? At each successful round, we win a factor , so the number of effective rounds is . So the total number of colors is at most
Take and this is .
Runtime is polynomial, since the expectation of the number of idle rounds is.
Best known approximation is (recent result of S. Arora, based on a better SDP).
2. Unique games
2.1. The problem
A unique game involves variables with values in . binary constraints (i.e. constraint involves 2 variables). In each constraint involving and , the value of is uniquely determined by the value of . Goal: maximize number of satisfied constraints.
Example 1 mod is a unique constraint. So systems of 2-variable linear equations over constitute unique games.
In fact, the unique games problem Karp-reduces to the linear unique games problem.
Note that the question wether , i.e. wether the set of constraints has a feasible assignment, has an easy answer: try a value for variable , and propagate it around using uniqueness. On the other hand, the question wether is close to or not seems hard.
2.2. Trevisan’s algorithm
The statement differs from previous ones, in that its scope is reduced: it applies only to special instances (those whose is close to the maximum ) but gives an approximation factor close to .
A similar theorem holds for MAX CUT. Both results are due to Luca Trevisan, 2005, [T].
2.3. The SDP
There is an implicit graph : vertices correspond to variables and edges to constraints. Each edge comes with the table of the permutation . Or a permutation matrix . Unknowns will be vectors (of unspecified dimension), indexed by pairs where is a vertex, . Change notation: abbreviate . Every vertex must have a single color, so let us impose
so that integral solutions correspond to vertex coloring. A coloring also satisfies for and for all . For every edge , the corresponding constraint reads (for feasible solutions, i.e. integral solutions of previous equations), so we want to maximize
Trick: we add constraints which provide us with a metric. The reason is that we are dealing with a multicutting problem and we want to mimic the technique for designing multicuts from balls in a metric.
These extra constraints are
They are satisfied by feasible solutions. This is our SDP.
2.4. The algorithm
1. Solve SDP relaxation.
2. Partition into balls of radius at most ( well chosen).
For all edges , let
This is a metric on .
While is not empty, take arbitrary vertex . Define
Choose to minimize where
Let . Add to the partition, remove from .
3. Rounding. Now we assign colors to vertices. For each ball, let us assign a color to the center , by picking it at random using the probability distribution . For other vertices in the ball, choose their color to minimize .
By construction, SDP is a relaxation.
Proof: We have:
When spans , by definition of unique games also spans , so equals . We use the first set of constraints of the SDP to infer . Summing over all constraints, is just minus the value of the SDP. The SDP is a relaxation, so its value is at least , and so is at most .
The next three lemmas follow closely our analysis of the multicut algorithms.
Proof: Let be the center of the ball. Assume, up to perturbating , that takes distinct values for all . Then is continuous, increasing, and piecewise linear, and it is easy to see that at every where is differentiable. Let . We have: at every where is differentiable.
By a variant of the mean value theorem, there exists an where is differentiable and such that is less than or equal to . Thus the ball added to the partition will also satisfy
Now, by definition of we have . On the other hand, is at most . Since is the shortest path metric defined by , we have . By definition of , we infer . Combining yields the lemma.
Proof: Every time the algorithm picks a ball as a part of the partition, the number of edges then discarded is . The total number is thus . By Lemma 3, this is at most . Using the definition of and the fact that ,
By Lemma 2, is at most . Combining gives the result.
Proof: Consider and for . By the last set of SDP constraints we can write:
Summing gives . Remembering the SDP orthogonality constraints, we can write , and, applying the SDP triangular inequality constraints, . Combining gives . Thus at most one of can be such that .
Here is the most important step.
Lemma 6 Let be a path between two vertices and . Choose label for with probability , and infer a label for by propagating labels along the path so that all constraints are satisfied. Then, with probability at least , the resulting label minimizes .
Proof: Let be the set of ‘s such that does not minimize . We want to upper bound . By Lemma 5, if then . By the SDP triangular inequality constraints,
where denotes the label of obtained by labeling with and propagating labels along the path so that all constraints are satisfied. The probability that the propagated label does not coincide with the assigned label is
The inner summation can be bounded by . By definition of unique games, when spans , also spans . Thus:
This implies the lemma.
Proof: Let be a shortest path from to , and consider the path from to . If the algorithm labels according to propagation along path and according to propagation along path , then constraint is satisfied. Apply Lemma 6 twice, to those two paths: since is a shortest path, the probability that the algorithm labels differently than by propagating along path is at most . The probability that the algorithm labels differently than by propagating along path is at most .
Proof: By Lemma 2 we have: . Since each term is non-negative, the number of terms greater than is at most .
To complete the proof of the Theorem, it only remains to bound the number of constraints not satisfied. There are three ways for constraints to not be satisfied: by Lemma 4, at most constraints are not inside balls of the partition; by Lemma 7, at most constraints are long; and by Lemma 8, in expectation, there are at most short constraints inside balls of the partition, for which propagation does not coincide with the choice of the labeling algorithm. This sums to
2.6. The Unique Games Conjecture
Trevisan’s Theorem 1 is significant only when . For fixed , can one find a fixed and an algorithm which, when applied to a unique game whose , outputs an assignment satisfying ? Roughly speaking, Subhash Khot’s Unique Games Conjecture claims that this is impossible. More precisely, the conjecture states that for every and , there exists a such that the following gap problem is NP-complete.
Given a unique game with labels such that or , decide which of the two cases holds.
For a slightly larger class of problems, Projection games, the corresponding gap problem is known to be NP-complete. So the Unique Games Conjecture (UGC) seems close to present knowledge. Nevertheless, is has so many striking consequences that it is hard to believe in it. For instance, it implies that the Goemans-Williamson approximation threshold 0.878… is sharp, S. Khot, G. Kindler, E. Mossel, R. O’Donnell 2007, [KKMO], see the first lecture in this series.
For more on UGC, see Khot’s talk in Cambridge this afternoon and the course of Sanjeev Arora and David Steurer in Paris next week.