Given a graph , we are trying to approximate the sparsest cut problem (which, in turn, approximates the edge expansion problem within a factor of two) defined as
And we have seen that an equivalent characterization of sparsest cut is:
In the Leighton-Rao relaxation, we have
where is the set of all semi-metrics , that is, of all functions such that , , and that obey the “triangle inequality”
for all .
This is clearly a relaxation of the sparsest cut problem, because for every the “distances” define indeed a semi-metric over .
How bad can the relaxation be? Take a family of regular constant-degree expander graphs, that is graphs where is a constant and the degree is a constant independent of . Define to be the shortest path distance between and in the graph. This is clearly a semi-metric, and we have
because along every edge the distance is precisely one, and
because, for every vertex , at most other vertices can be within
distance , and so at least half the vertices are at distance .
So we have
even though , so the error in the approximation can be as bad as a factor of . We shall prove that this is as bad as it gets.
Our task is then: given a feasible solution to (2), that is, a distance function defined on the vertices of , find a feasible solution to sparsest cut whose cost is as small as possible, and no more than a factor off from the cost of the solution to (2) that we started from. Instead of directly looking for a cut, we shall look for a solution to (1), which is a more flexible formulation.
The general strategy will be, given , to find a distribution over vectors such that for every two vertices we have
Suppose that we start from a solution to (2) of cost , that is, we have a semimetric such that
Then our distribution is such that
and there must exist a vector in the support of the distribution such that
and now we are done because the cost of in (1) is at most times the optimum of the Leighton-Rao relaxation.
Though this works, it seems an overkill to require condition (3) for all pairs of vertices. It seems sufficient to require
only for edges, and to require
only “on average” over all pairs of vertices. It can be shown, however, that if one wants to round a generalization of the Leighton-Rao relaxation to sparsest cut with “non-uniform demands,” then any rounding algorithm can be turned into a rounding algorithm that satisfies (3).
So how do we start from an arbitrary metric and come up with a probabilistic linear order of the vertices so that their distances in the original metric are well approximated in the linear ordering? We will describe a method of Bourgain, whose applicability in this setting is due Linial, London and Rabinovich.
The starting point is to see that if is a set of vertices, and we define
then, no matter how we choose , we always have
[Hint: use the triangle inequality to see that .]
This means that “all we have to do” is to find a distribution over sets such that for every we have
If you want to make it sound more high-brow, you may call such a distribution a Frechet embedding of into . Constructing such a distribution will be the subject of the next post.