## Sparsest Cut via Metric Embeddings

A very powerful technique to design approximation algorithms is called metric embeddings. A lot of problems are easy when the graph has some special structure like a tree or a cycle or when the vertices are encoded as points in a . This gives us more structure to the problem an allows us to make geometric considerations about the object we are studying – and this is sometimes the key to find a good approximation. The basic idea is to start with a space without much structure and try to approximate it by some space with stronger geometric or topological properties. A lot has be done recently in finding cuts in graphs or solving Steiner Tree problems.

Consider the problem of finding the sparsest cut in a graph. Given a graph , we define the sparsity of a as:

where is the set of edges with one endpoint in and other in . The *sparsest cut* is the cut minimizing the sparsity. A related problem is the *flux* problem, which asks for a cut minimizing:

If we can minimize flux, we have a -approximation for sparsity, since for all we have that: . If we can approximate the minimum flux, we can also approximate sparsity by the same factor multiplied by .

Let’s formulate flux as an embeddings problem: we would like a mapping such that minimizes:

Let’s relax this a bit. Substitue by . So, we want to minimize . A standard trick for minimizing fractions where both numerator and denominator are linear functions on the same variables is to fix the denominator to be and minimize the denominator. So, we want to minimize given that . We also wanted . But this is still not enough, we want to be of a specific form called cut metric, i.e., there is a partition of in two sets and iff and are in different sets. We relax it a bit by just asking it to be a metric, i.e, non-negative value so that the triangle inequality holds:

By relaxing a minimization problem we might get a solution which has actually smaller than the previous problem. This gives however a lower bound to the result. In general, finding a good lower bound is the first step in the analysis of approximation algorithms.

Theorem 1The solution of the flux problem is lower-bounded by the solution of the following LP:

The idea for approximating this is to drop the integrality constraint, solve the LP to get a general metric and the round it to obtain a cut. Suppose is the optimal solution to the LP version of the program above. How to get a cut from it?

To do it, we will use a powerful result due to Bourgain, but first, let’s discuss some basics about metrics and embeddinds. A metric space is a pair where is a set and . Examples of metric spaces are:

- is the set of vertices of a weighted graph and is the distance from to in the graph;
- and is the -norm, i.e., , when , this is the Euclidian norm, when , it is the Manhattan distance. This space is called ;
- and is the -norm, i.e., . It is called norm, because it where denoted the distance in the norm. This space is called

Given two metric spaces and , we say that a mapping is a distortion embedding:

to make our life easier, we use most of the times the following (not so) weaker definition: we say it is a distortion embedding if there is some factor such that:

this is the same but allowing some scaling.

Bourgain’s Theorem says that:

Theorem 2 (Bourgain)For any metric space with there is an embedding into with distortion . And we can construct this embedding in poly-time using a randomized algorithm.

Supose is such embedding. Then we have a function such that . Now, this gives us cuts obtained in the following way: for each coordinate of , order the points according to and for each take the cut formed by the first points. Let this be the cut Then, take the minimum of those cuts.

Theorem 3The procedure described above generates a cut within a factor of to the optimal in poly-time.

To prove this, first we need some notation. Given the cut , let be the cut-distance associated with it, i.e., is if and are in the same side of the cut and otherwise. Let also . It is not difficult to see that:

and, therefore:

Now, we can go ahead and prove the theorem: Let be the optimal flux and the flux obtained by the algorithm. We have that:

where . Then:

but this is exacly the expression of -norm, so:

which is smaller than since this is the solution to the LP, which is a relaxed version of the original problem. And this finishes the proof.

This is one of the first applications to metric embeddings. It was introduced in a paper by Linal, London and Rabinovich. There are very nice resources on the web about metric embeddins, as the course by Anupam Gupta at CMU, the course by Michael Goemans at MIT and the course by Tim Roughgarden at Stanford.

This is also an area full of exciting open problems. It is known, for example, that it is hard to decide if a given metric is embeddable in or not. But given a metric that we know that is isometrically embeddable in , how to find the embedding? This is an open problem. In fact, it is unknown even how to approximate this embedding by a factor better then , which is given by Bougain’s Theorem.