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