## Notes of Sanjeev Arora’s lecture nr 1

Graph expansion, Unique Games

1. Graph expansion

Given a graph, one wants to cut it into two parts and minimize the number of deleted edges. Without restrictions on the size of ${S}$, this is MIN CUT, which has a polynomial solution. There are many variants, like

• minimizing conductance ${\frac{E(S,\bar{S}}{|S||\bar{S}|}}$;
• minimizing edge expansion ${\frac{E(S,\bar{S})}{|S|}}$;
• minimizing ${\frac{1}{4}}$-balanced expansion ${\frac{E(S,\bar{S})}{|S|}}$ for ${S}$ such that ${\frac{1}{4}|V|\leq |S|\leq \frac{1}{2}|V|}$.

All these are NP-hard. If you solve some of them efficiently, this helps for many other problems, thanks to the divide and conquer strategy. So these are model problems.

1.1. Methods

• Classic : Eigenvalues
• 1988 : Leighton and Rao, [LR], Linear Programming based, gave a ${O(\log n)}$ approximation.
• 1994 : reinterpreted by Linial, London and Rabinovich, [LLR], in the language of geometric embeddings.
• 2004 two approaches by Arora, Rao, Vazirani, [ARV], SDP and expander flows, giving ${O(\sqrt{\log n})}$. I will spend more time on the expander flow method, since it is less well known and more interesting mathematically.
• Extensions of these methods were given by Arora, Lee and Naor, [ALN], and Chawla, Gupta and Räcke, [CGR] in 2005.

Nice interplay

1.2. Eigenvalues

Rephrase conductance as

$\displaystyle \begin{array}{rcl} \frac{\sum_{ij\in E}(x_i -x_j)^2}{\sum_{i

This is scale invariant, so the relaxation does not require any bounds, ${x_i \in {\mathbb R}}$. This is translation invariant, so one may add ${\sum_{i}x_i =0}$.

Although quadratic, this can be approximated in polynomial time. Indeed, for regular graphs, this is the first nonzero eigenvalue ${\lambda}$ of the Laplacian (let us assume ${G}$ is regular, from now on; one can easily reduce to this case).

Cheeger’s inequality (Alon -M) states that

$\displaystyle \begin{array}{rcl} \Omega(\alpha_{G}^{2})\leq \lambda\leq O(\alpha_G). \end{array}$

This is a good approximation if ${\alpha_G}$ does not tend to zero, e.g., for expanders.

1.3. Flow based approach

Think of graph as traffic network. One expects congested edges to give an efficient cut. Not rigorously right, however.

Introduce one flow variable ${f_{ijp}}$ for each path and pair of vertices: ${f_{ijp}}$ is the flow from ${i}$ to ${j}$ on path ${p}$. Capacity constraint is

$\displaystyle \begin{array}{rcl} \sum_{e\subset p}\sum_{ij}f_{ijp}\leq 1. \end{array}$

Say that flow is ${\delta}$-regular if

$\displaystyle \begin{array}{rcl} \forall i,\quad \sum_{i}\sum_{p}f_{ijp}=\delta. \end{array}$

then for all cuts ${S}$ of size ${\leq \frac{1}{2}|V|}$, the total flow from ${S}$ to its complement ${\bar{S}}$,

$\displaystyle \begin{array}{rcl} f(S,\bar{S})\geq \frac{\delta}{10}|S|. \end{array}$

This implies that ${|E(S,\bar{S})|\geq \frac{\delta}{10}|S|}$.

It looks circular, but we win something by replacing graph geometry by flow geometry, thanks to Cheeger’s inequality.

Sanjeev Arora, Satish Rao and Umesh Vazirani, [ARV], prove the following theorem.

Theorem 1 If ${\alpha_G}$ denotes edge expansion, then the LP is feasible (i.e. there exists a ${\delta}$-regular flow) for ${\delta=\frac{\alpha_G}{100\sqrt{\log n}}}$.

Although the LP has exponential size, there is an approximate separation oracle, thanks to Cheeger’s inequality, so there is a polytime solution.

Proof: Use Farkas Lemma (criterion for feasibility of an LP). Prove that for all graphs ${H}$ of edge expansion ${\beta}$, for all embeddings ${v_1 ,\ldots,v_n}$ of ${H}$ in the unit ball ${B_{\ell_1}}$ satisfying

$\displaystyle \begin{array}{rcl} \sum_{i

there exist ${\frac{n}{10}}$ disjoint pairs ${(i_1 ,j_1),\ldots,(i_{n/10},j_{n/10})}$ such that

$\displaystyle \begin{array}{rcl} d_H (i_{\ell},i_{\ell})\leq 100\frac{\sqrt{\log n}}{\beta} \end{array}$

and

$\displaystyle \begin{array}{rcl} |v_{i_\ell}-v_{j_\ell}|\geq\frac{1}{1000}. \end{array}$

Looks bizarre ? Here is where the ${\ell_1}$ embedding comes from. The combination of inequalities à la Farkas involves one nonnegative coefficient per cut. Thus a convex combination of cut-metrics, thus an ${\ell_1}$ metric. The term ${\frac{\sqrt{\log n}}{\beta}}$ is explained as follows. ${1/\beta}$ is a lower bound on the average distance in ${H}$. Getting ${\frac{\log n}{\beta}}$ is easy, getting ${\frac{\sqrt{\log n}}{\beta}}$ is harder. $\Box$

1.4. The SDP relaxation

It is an other relaxation of conductance. Let scalars ${x_i}$ be replaced by vectors in Euclidean space. Minimize

$\displaystyle \begin{array}{rcl} \frac{\sum_{ij\in E}(v_i -v_j)^2}{\sum_{i

Add the triangle inequality

$\displaystyle \begin{array}{rcl} |v_i -v_j|^2 +|v_j -v_k|^2 \geq |v_i -v_k|^2 . \end{array}$

This computes a ${\sqrt{\log n}}$-approximation too. This follows from a geometric theorem.

Theorem 2 Let ${v_1,\ldots,v_n}$ be unit vectors satisfying

$\displaystyle \begin{array}{rcl} |v_i -v_j|^2 +|v_j -v_k|^2 \geq |v_i -v_k|^2 . \end{array}$

Define a graph: put an edge between ${i}$ and ${j}$ if ${|v_i -v_j|^2 \leq\Delta}$. If ${\Delta <\frac{1}{100\sqrt{\log n}}}$, the graph cannot be an expander.

Assuming Theorem 2, let us prove Theorem 1, i.e. that the integrality gap of the SDP relaxation is ${O(\sqrt{\log n})}$.

Since the graph produced by Theorem 2 is not an expander, there exists a relatively large subset ${S}$ of vertices with small expansion, i.e. for every pair ${i\in S}$, ${j\notin S}$, ${|v_i -v_j|\geq \Omega(\frac{1}{100\sqrt{\log n}})}$. Let ${V_s}$ denote the set of points at distance ${s}$ of ${S}$ in ${H}$ and ${E_s}$ the set of edges leaving ${V_s}$. Pick ${s_0\leq \frac{1}{100\sqrt{\log n}}}$ that minimizes ${|E_s|/|V_s|}$ and output the cut ${V_{s_0}}$. The sum ${\sum_s |E_s|}$ is less than the ${OPT}$ of the SDP, so expansion is ${\leq O(\sqrt{\log n)}OPT}$.

References

[ALN] Arora, Sanjeev; Lee, James; Naor, Assaf; Euclidean distortion and the Sparsest Cut. J. Amer. Math. Soc. 21 (2008), no. 1, 1–21.

[ARV] Arora, Sanjeev; Rao, Satish; Vazirani, Umesh; Expander flows, geometric embeddings and graph partitioning. J. ACM 56 (2009), no. 2, Art. 5, 37 pp.

[CGR] Chawla, Shuchi; Gupta, Anupam; Räcke, Harald; Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms 4 (2008), no. 2, Art. 22, 18 pp.

[LLR] Linial, Nathan; London, Eran; Rabinovich, Yuri; The geometry of graphs and some of its algorithmic applications. Combinatorica 15 (1995), no. 2, 215–245.

[LR] Leighton, Tom; Rao, S.; An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. FOCS 29 (1988), 422–431.