**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 , this is MIN CUT, which has a polynomial solution. There are many variants, like

- minimizing
*conductance*; - minimizing
*edge expansion*; - minimizing
*-balanced expansion*for such that .

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 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 . 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

This is scale invariant, so the relaxation does not require any bounds, . This is translation invariant, so one may add .

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

Cheeger’s inequality (Alon -M) states that

This is a good approximation if 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 for each path and pair of vertices: is the flow from to on path . Capacity constraint is

Say that flow is *-regular* if

then for all cuts of size , the total flow from to its complement ,

This implies that .

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 1If denotes edge expansion, then the LP is feasible (i.e. there exists a -regular flow) for .

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 of edge expansion , for all embeddings of in the unit ball satisfying

there exist disjoint pairs such that

and

Looks bizarre ? Here is where the embedding comes from. The combination of inequalities *à la Farkas* involves one nonnegative coefficient per cut. Thus a convex combination of cut-metrics, thus an metric. The term is explained as follows. is a lower bound on the average distance in . Getting is easy, getting is harder.

** 1.4. The SDP relaxation **

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

Add the triangle inequality

This computes a -approximation too. This follows from a geometric theorem.

Theorem 2Let be unit vectors satisfying

Define a graph: put an edge between and if . If , 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 .

Since the graph produced by Theorem 2 is not an expander, there exists a relatively large subset of vertices with small expansion, i.e. for every pair , , . Let denote the set of points at distance of in and the set of edges leaving . Pick that minimizes and output the cut . The sum is less than the of the SDP, so expansion is .

** 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.