Notes of Claire Mathieu’s lecture nr 4

1. An ${n^{1/4}}$ times polylog-approximation for coloring ${3}$-colorable graphs

1. Reduce degree as before.

2. Recall the SDP relaxation we used on wednesday. Minimize ${0}$ under constraints ${v_i \cdot v_j =-1/2}$, ${|v_i|^2 =1}$. Today, we merely change the rounding procedure.

3. Rounding. Let ${\alpha, \Delta_0, \delta}$ be well-chosen values, ${\alpha \geq 1}$. While max degree ${>\Delta_0}$, pick a random Gaussian vector ${r}$. Consider the affine (i.e. does not go through the origin) hyperplane normal to ${r}$ defined by ${V\cdot r \geq \alpha}$. It isolates a part ${R}$ of the vertices,

$\displaystyle \begin{array}{rcl} \{i\,;\,v_i \cdot r\geq \alpha\} \end{array}$

which need not form an independant set. So take

$\displaystyle \begin{array}{rcl} S_R =\{i\,;\,v_i \in R,\,\forall j\sim i,\,v_j \notin R\}, \end{array}$

color ${S_R}$ in one color and remove it.

4. Color remainder with ${\Delta_0}$ colors.

Analysis. Since the Gaussian density is rotation invariant and a tensor product of one variable Gaussians,

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(i\in R)=\mathop{\mathbb P}(r\cdot v_i \geq\alpha)=\int_{\alpha}^{+\infty}\frac{1}{\sqrt{2\pi}}e^{-x^2 /2}dx:=\Phi(\alpha). \end{array}$

Since ${v_j \cdot v_i =-1/2}$, ${v_j =-\frac{1}{2}v_i +\frac{\sqrt{3}}{2}u}$ where ${u}$ is unit and orthogonal to ${v_i}$. So ${r\cdot v_j=-\frac{1}{2}+\frac{\sqrt{3}}{2}r\cdot u}$, where the normal Gaussian random variable ${r\cdot u}$ is independant from ${r\cdot v_i}$. So the conditional probability

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(j\in R\,|\,i\in R)=\mathop{\mathbb P}(r\cdot u\geq \sqrt{3}\alpha\,|\,r\cdot v_i \geq\alpha) =\mathop{\mathbb P}(r\cdot u\geq \sqrt{3}\alpha)=\Phi(\sqrt{3}\alpha). \end{array}$

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(i\in S_R \,|\, i\in R)&=&\mathop{\mathbb P}(\forall j\sim i,\,j\notin R|i\in R)\\ &=&1-\mathop{\mathbb P}(\exists...)\\ &\geq& 1-\sum_{j\sim i}\mathop{\mathbb P}(j\in R\,|\,i\in R)\\ &\geq& 1-\sum_{j\sim i}\Phi(\sqrt{3}\alpha)\\ &\geq& 1-\Delta\Phi(\sqrt{3}\alpha), \end{array}$

where ${\Delta}$ is the maximum degree. Choose ${\alpha}$ so that ${1-\Delta\Phi(\sqrt{3}\alpha)=1/2}$. We shall use the rough estimates, for ${t\geq \alpha}$

$\displaystyle \begin{array}{rcl} \frac{1}{2t\sqrt{2\pi}}e^{-t^2 /2}\leq\Phi(t)\leq \frac{1}{t\sqrt{2\pi}}e^{-t^2 /2}. \end{array}$

The upper bound gives

$\displaystyle \begin{array}{rcl} \alpha=\sqrt{\frac{2}{3}\log(\frac{2\Delta}{\sqrt{6\pi}})}. \end{array}$

Using the lower bound, we get

$\displaystyle \begin{array}{rcl} \mathop{\mathbb E}(|S_R|)\geq\sum_{i}\mathop{\mathbb P}(i\in R).\frac{1}{2}\geq const.\frac{n'}{\Delta^{1/3}\log\Delta}:=\delta n', \end{array}$

where ${n'}$ is the current number of vertices (remember that we keep discarding vertices once colored). Markov inequality applied to ${Z=n'-|S_R|}$ gives

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(Z>(1-\frac{\delta}{2})n')<\frac{\delta}{2}. \end{array}$

If this happens, we do nothing. Else, we remove ${S_R}$, and ${n'}$ decreases at least by a factor ${\delta/2}$.

How many colors have been used ? At each successful round, we win a factor ${1-\frac{\delta}{2}}$, so the number of effective rounds is ${\leq \log(n)/\log(1-\frac{\delta}{2})\simeq \frac{2}{\delta}\log n}$. So the total number of colors is at most

$\displaystyle \begin{array}{rcl} \frac{n}{\Delta}+\Delta^{1/3}\log\Delta\log n. \end{array}$

Take ${\Delta=n^{3/4}}$ and this is ${O(n^{1/4}(\log n)^2)}$.

Runtime is polynomial, since the expectation of the number of idle rounds is.

Best known approximation is ${\tilde{O}(n^{.211...})}$ (recent result of S. Arora, based on a better SDP).

2. Unique games

2.1. The problem

A unique game involves ${n}$ variables with values in ${\{1,\cdots,k\}}$. ${m}$ binary constraints (i.e. constraint involves 2 variables). In each constraint involving ${x_i}$ and ${x_j}$, the value of ${x_i}$ is uniquely determined by the value of ${x_j}$. Goal: maximize number of satisfied constraints.

Example 1 ${x_i +x_j =2}$ mod ${k}$ is a unique constraint. So systems of 2-variable linear equations over ${\mathbb{F}_k}$ constitute unique games.

In fact, the unique games problem Karp-reduces to the linear unique games problem.

Note that the question wether ${OPT=m}$, i.e. wether the set of constraints has a feasible assignment, has an easy answer: try a value for variable ${x_1}$, and propagate it around using uniqueness. On the other hand, the question wether ${OPT}$ is close to ${1}$ or not seems hard.

2.2. Trevisan’s algorithm

Theorem 1 There is an algorithm which, when applied to a unique game whose ${OPT\geq (1-\epsilon)m}$, outputs an assignment satisfying ${\geq (1-O(\sqrt{\epsilon \log n}))m}$ constraints.

The statement differs from previous ones, in that its scope is reduced: it applies only to special instances (those whose ${OPT}$ is close to the maximum ${m}$) but gives an approximation factor close to ${1}$.

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 ${G}$: vertices correspond to variables and edges to constraints. Each edge ${e=ij}$ comes with the table of the permutation ${x_i \mapsto x_j}$. Or a permutation matrix ${\pi_e}$. Unknowns will be vectors ${v_{ui}}$ (of unspecified dimension), indexed by pairs ${(u,i)}$ where ${u}$ is a vertex, ${i\in\{1,\ldots,k\}}$. Change notation: abbreviate ${v_{ui}=u_i}$. Every vertex must have a single color, so let us impose

$\displaystyle \begin{array}{rcl} \sum_{i=1}^{k}|u_i|^2 =1, \end{array}$

so that integral solutions correspond to vertex coloring. A coloring also satisfies ${u_i \cdot u_j =0}$ for ${i\not=j}$ and ${u_i \cdot v_j \geq 0}$ for all ${u,v,i,j}$. For every edge ${e=uv}$, the corresponding constraint reads ${u_i \cdot v_{\pi_{e}(i)}=1}$ (for feasible solutions, i.e. integral solutions of previous equations), so we want to maximize

$\displaystyle \begin{array}{rcl} Cost=\sum_{e=uv}\sum_{i=1}^{k}u_i \cdot v_{\pi_{e}(i)}. \end{array}$

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

$\displaystyle \begin{array}{rcl} |w_h -u_i|^2 &\leq& |w_h -v_j|^2 +|v_j -u_i|^2 ,\\ |v_i -u_j|^2 &\geq&|v_i|^2 -|u_j|^2. \end{array}$

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 ${\delta/4}$ (${\delta}$ well chosen).

For all edges ${uv}$, let

$\displaystyle \begin{array}{rcl} \ell(u,v)=\frac{1}{2}\sum_{i=1}^{k}|u_i - v_{\pi_{e}(i)}|^2 . \end{array}$

This is a metric on ${G}$.

While ${G}$ is not empty, take arbitrary vertex ${w}$. Define

$\displaystyle \begin{array}{rcl} B(w,r)=\{v\,;\,\ell(w,v)\leq r\},\quad c(r)=|\{uv\in E\,;\,u\in B,\,v\notin B\}|. \end{array}$

Choose ${r\leq \delta/4}$ to minimize ${\frac{c(r)}{V(w,r)}}$ where

$\displaystyle \begin{array}{rcl} V(w,r)=V_0 +\sum_{ \{ u,v \}\in E, u,v\in B} |d(w,v)-d(w,u)| + \sum_{ \{ u,v\}\in E, u\in B, v\notin B } r-d(w,u). \end{array}$

Let ${V_0 =\frac{1}{n}\sum_{uv\in E}\ell(u,v)}$. Add ${B}$ to the partition, remove ${B}$ from ${G}$.

Choose ${\delta = \sqrt{\epsilon \log (n+1)}}$.

3. Rounding. Now we assign colors to vertices. For each ball, let us assign a color to the center ${w}$, by picking it at random using the probability distribution ${i\mapsto |w_i|^2}$. For other vertices ${u}$ in the ball, choose their color ${j}$ to minimize ${|w_i -u_j|^2}$.

2.5. Analysis

By construction, SDP is a relaxation.

Lemma 2 Assume there is an assignment satisfying ${\geq(1-\epsilon)m}$ constraints. Then

$\displaystyle \begin{array}{rcl} L^* :=\sum_{uv\in E}\ell(u,v)\leq\epsilon m. \end{array}$

Proof: We have:

$\displaystyle \ell(u,v)={1\over 2} \sum_{1\leq i\leq k} |u_i|^2 + |v_{\pi_{uv}(i)}|^2 - 2u_i\cdot v_{\pi_{uv}(i)} .$

When ${i}$ spans ${\{ 1,\ldots ,k\}}$, by definition of unique games ${\pi_{uv}(i)}$ also spans ${\{ 1,\ldots ,k\}}$, so ${\sum_{1\leq i\leq k}|v_{\pi_{uv}(i)}|^2}$ equals ${ \sum_{1\leq j\leq k} |v_j|^2}$. We use the first set of constraints of the SDP to infer ${\ell(u,v)= 1- \sum_{1\leq i\leq k} u_i \cdot v_{\pi_{uv}(i)}}$. Summing over all constraints, ${L^*}$ is just ${m}$ minus the value of the SDP. The SDP is a relaxation, so its value is at least ${(1-\epsilon )m}$, and so ${L^*}$ is at most ${\epsilon m}$. $\Box$

The next three lemmas follow closely our analysis of the multicut algorithms.

Lemma 3 Let ${B}$ be a ball added to the partition. Then ${c(B)\leq {4\over \delta} \log (n+1) V(B)}$.

Proof: Let ${w}$ be the center of the ball. Assume, up to perturbating ${\ell}$, that ${d(w,u)}$ takes distinct values for all ${u}$. Then ${V(r)}$ is continuous, increasing, and piecewise linear, and it is easy to see that ${V'(r)=c(r)}$ at every ${r}$ where ${V}$ is differentiable. Let ${f(r)=\log V(r)}$. We have: ${f'(r)=c(r)/V(r)}$ at every ${r}$ where ${V}$ is differentiable.

By a variant of the mean value theorem, there exists an ${r\in [0,\delta /4)}$ where ${f}$ is differentiable and such that ${c(r)/V(r)}$ is less than or equal to ${(f(\delta/4)-f(0))/(\delta/4)}$. Thus the ball added to the partition will also satisfy

$\displaystyle {c(B)\over V(B)}\leq {f(\delta/4)-f(0)\over \delta/4}.$

Now, by definition of ${V}$ we have ${f(0)=\log (L^*/n)}$. On the other hand, ${f(\delta/4)}$ is at most ${f(\infty )= \log ( L^*/n+ \sum_{ \{ u,v \}\in E} |d(w,v)-d(w,u)|)}$. Since ${d}$ is the shortest path metric defined by ${\ell}$, we have ${ |d(w.v)-d(w,u)|\leq \ell (u,v)}$. By definition of ${L^*}$, we infer ${f(\delta/4)\leq \log (L^*/n + L^*)}$. Combining yields the lemma. $\Box$

Lemma 4 Assume that there exists an assignment satisfying ${(1-\epsilon )m}$ constraints. Then the total number of edges not inside parts of the partition is at most ${(8/ \delta ) \log (n+1) \epsilon m}$.

Proof: Every time the algorithm picks a ball ${B=B(w,r)}$ as a part of the partition, the number of edges then discarded is ${c(r)}$. The total number is thus ${\sum_{B(w,r)\text{ in partition}} c(r)}$. By Lemma 3, this is at most ${(4/ \delta ) \log (n+1) \sum V(B(w,r))}$. Using the definition of ${V(B)}$ and the fact that ${|d(w,v)-d(w,u)|\leq \ell (u,v)}$,

$\displaystyle \sum_{B(w,r)\text{ in partition}}V(B(w,r)) \leq ( L^* + \sum_{ \{ u,v\}\in E} \ell (u,v)) = 2 L^*.$

By Lemma 2, ${L^*}$ is at most ${\epsilon m}$. Combining gives the result. $\Box$

Lemma 5 Let ${w,u\in V}$ and let ${i\in \{ 1,\ldots ,k\}}$. Then there is at most one index ${j}$ such that ${|w_i-u_j|^2 < (1/2) |w_i|^2}$.

Proof: Consider ${u_j}$ and ${u_h}$ for ${j\neq h}$. By the last set of SDP constraints we can write:

$\displaystyle \begin{array}{rcl} \begin{cases} |w_i|^2\leq |u_j|^2+ |w_i-u_j|^2 & \\ |w_i|^2\leq |u_h|^2+ |w_i-u_h|^2. & \end{cases} \end{array}$

Summing gives ${2|w_i|^2\leq |w_i-u_j|^2+ |w_i-u_h|^2 + |u_j|^2+|u_h|^2}$. Remembering the SDP orthogonality constraints, we can write ${|u_j|^2+|u_h|^2=|u_j-u_h|^2}$, and, applying the SDP triangular inequality constraints, ${|u_j-u_h|^2\leq |u_j-w_i|^2+|w_i-u_j|^2}$. Combining gives ${|w_i|^2\leq |w_i-u_j|^2+ |w_i-u_h|^2}$. Thus at most one of ${u_j,u_h}$ can be such that ${|w_i-u_j|^2 < (1/2) |w_i|/2}$. $\Box$

Here is the most important step.

Lemma 6 Let ${(w=u^0,u^1, u^2,\ldots ,u^T=u)}$ be a path between two vertices ${w}$ and ${u}$. Choose label ${i}$ for ${w}$ with probability ${|w_i|^2}$, and infer a label ${h}$ for ${u}$ by propagating labels along the path so that all constraints are satisfied. Then, with probability at least ${1-4\sum_t \ell(u^t,u^{t+1})}$, the resulting label ${h}$ minimizes ${|w_i-u_h|^2}$.

Proof: Let ${I}$ be the set of ${i}$‘s such that ${h}$ does not minimize ${|w_i-u_h|^2}$. We want to upper bound ${P=\sum_{i\in I} |w_i|^2}$. By Lemma 5, if ${i\in I}$ then ${|w_i|^2 \leq 2 |w_i-u_h|^2}$. By the SDP triangular inequality constraints,

$\displaystyle |w_i-u_h|^2\leq \sum_t |u^t_{\pi (i,t)} - u^{t+1}_{\pi (i,t+1)}|^2,$

where ${\pi(i,t)}$ denotes the label of ${u^t}$ obtained by labeling ${w}$ with ${i}$ and propagating labels along the path ${u^0,u^1,\ldots ,u^t}$ so that all constraints are satisfied. The probability that the propagated label does not coincide with the assigned label is

$\displaystyle \begin{array}{rcl} P:&=&\sum_{i\in I}|w_i|^{2}\\ &\leq&\sum_{i\in I}2|w_i-u_h|^2 \\ &\leq& 2 \sum_{t\mathrm{\,along\,path}} \sum_{i\in I} |u^t_{\pi (i,t)} - u^{t+1}_{\pi (i,t+1)}|^2. \end{array}$

The inner summation can be bounded by ${\sum_{1\leq i\leq k} |u^t_{\pi (i,t)} - u^{t+1}_{\pi (i,t+1)}|^2}$. By definition of unique games, when ${i}$ spans ${\{ 1,\ldots k\}}$, ${\pi (i,t)}$ also spans ${\{ 1,\ldots ,k\}}$. Thus:

$\displaystyle \sum_{1\leq i\leq k} |u^t_{\pi (i,t)} - u^{t+1}_{\pi (i,t+1)}|^2= \sum_{1\leq j\leq k} |u^t_{j} - u^{t+1}_{\pi _{u^tu^{t+1}}(j)}|^2= \ell (u^t,u^{t+1}).$

This implies the lemma. $\Box$

Lemma 7 Let ${B=B(w,r)}$ be a ball of the partition. Let ${\{ u,v\}\in E}$ where ${u,v\in B(w,r)}$ and ${\ell (u,v)\leq \delta/2}$. Then the probability that constraint ${\{ u,v \}}$ is not satisfied by the algorithm is at most ${4\delta}$.

Proof: Let ${p=(w=u^0,u^1,\ldots ,u^T=u)}$ be a shortest path from ${w}$ to ${u}$, and consider the path ${p'=(u^0,u^1,\ldots ,u^T, u^{T+1}=v)}$ from ${w}$ to ${v}$. If the algorithm labels ${u}$ according to propagation along path ${p}$ and ${v}$ according to propagation along path ${p'}$, then constraint ${\{ u,v\}}$ is satisfied. Apply Lemma 6 twice, to those two paths: since ${p}$ is a shortest path, the probability that the algorithm labels ${u}$ differently than by propagating along path ${p}$ is at most ${4 \text{length}(p)= 4d(w,u)\leq \delta}$. The probability that the algorithm labels ${v}$ differently than by propagating along path ${p'}$ is at most ${4(\text{length}(p)+\ell (u,v))\leq 3\delta}$. $\Box$

Lemma 8 Assume that there exists an assignment satisfying ${(1-\epsilon )m}$ constraints. Then at most ${(2\epsilon /\delta )m}$ constraints have ${\ell (u,v)> \delta /2}$.

Proof: By Lemma 2 we have: ${\sum_{ \{ u,v \} \in E} \ell (u,v)\leq \epsilon m}$. Since each term is non-negative, the number of terms greater than ${\delta /2}$ is at most ${(2\epsilon /\delta )m}$. $\Box$

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 ${(8/ \delta ) \log (n+1) \epsilon m}$ constraints are not inside balls of the partition; by Lemma 7, at most ${(2\epsilon /\delta )m}$ constraints are long; and by Lemma 8, in expectation, there are at most ${4\delta m}$ short constraints inside balls of the partition, for which propagation does not coincide with the choice of the labeling algorithm. This sums to

$\displaystyle \left( {8\epsilon \log (n+1)\over\delta} + {2\epsilon \over\delta} + 4\delta \right)m= O(m\sqrt{\epsilon \log n} )$

since ${\delta=\sqrt{\epsilon\log (n+1)}}$.

2.6. The Unique Games Conjecture

Trevisan’s Theorem 1 is significant only when ${\epsilon<1/\log n}$. For fixed ${\epsilon>0}$, can one find a fixed ${\delta>0}$ and an algorithm which, when applied to a unique game whose ${OPT\geq (1-\epsilon)m}$, outputs an assignment satisfying ${\geq \delta m}$ ? Roughly speaking, Subhash Khot’s Unique Games Conjecture claims that this is impossible. More precisely, the conjecture states that for every ${\epsilon>0}$ and ${\delta>0}$, there exists a ${k=k(\epsilon,\delta)}$ such that the following gap problem is NP-complete.

Given a unique game with ${k}$ labels such that ${OPT\geq (1-\epsilon)m}$ or ${OPT\leq \delta m}$, 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.

References

[KKMO] Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O’Donnell, Ryan; Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37 (2007), no. 1, 319–357.

[T] Trevisan, Luca; Approximation Algorithms for Unique Games. Proc. of the 46th IEEE FOCS, 2005.

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Course and tagged . Bookmark the permalink.

2 Responses to Notes of Claire Mathieu’s lecture nr 4

1. Riikka says:

Could you clarify the beginning of the chapter 2.3. The SDP?

I did not completely understand the setting: for variables we picked {k} vectors for each vertex {u} in the graph. But why? What do the vectors {u_i} refer to? Their length seems not to be of importance, not even defined. Why does

\displaystyle \begin{array}{rcl} \sum_{i=1}^{k}|u_i|^2 =1, \end{array}

impose that every vertex has a single colour? And what does an integral solution mean?

BTW, there is a missprint:
“Unknown will vectors {v_{ui}}, {u} vertex, {i\in\{1,\ldots,k\}}.”
-> probably “Unknowns will be vectors etc”.

• metric2011 says:

Dear Riikka,

Thanks for proofreading these notes and pointing to mistakes in the notes that make them impossible to understand.

The first step in an SDP approach to an optimisation problem is to embed the given problem in a semidefinite program. This means mapping unknowns of the combinatorial problem to unknowns of the semidefinite program in such a way that objective functions coincide.

Here, the unknowns of the combinatorial problem are k-colorings. Suppose we view a k-coloring as a vector in R^n, whose components are integers between 1 and k. When relaxing the integrality assumption, the number k, which is essential for the combinatorial problem, disappears. The optimum of the SDP does not depend on k. This does not seem to be a good idea.

In order to freeze k in the SDP, Luca Trevisan had the idea to include it as a dimension. He chooses unknowns of the SDP to be nk-tuples of vectors. Note that the dimension of the vectorspace where these vectors live is unspecified. This is a rule for SDP’s: the true unknown is the Gram matrix X (whose entries are pairwise inner products) of the collection of vectors. Individual vectors (columns of a matric V) appear only when one expresses X as X=V^top V, they are defined only up to rotation, and their dimension, the rank of X, is apriori unknown.

A coloring v (i.e. a {1,…,k}-valued function on vertices) is mapped to an nk-tuple of vectors as follows: given a vertex u and a color i, set u_i to be the vector with one component, equal to zero unless v(u)=i, in which case it is 1.

The objective function is the number of satisfied constraints, which can be rewritten as
\sum_{e=uv}\sum_{i=1}^{k}u_i \cdot v_{\pi_{e}(i)}.

Next, one collects semidefinite constraints satisfied by such very special k-tuples of vectors.
1. For all vertices u, v and colors i, j, inner product u_i . v_j is nonnegative.
2. If i and j are distinct colors, and u is a vertex, then the inner product u_i . u_j vanishes.
3. For every vertex u, only one of the vectors u_i is non zero, so \sum_{i=1}^k |u_i|^2 =1.
4. Triangle inequalities.

The collection of these constraints constitutes the SDP.

Sincerely,