[In which we finally get to Leighton-Rao and ARV.]
Continuing our edge expansion marathon, we are going to see more ways in which the sparsest cut problem can be relaxed to polynomial-time solvable continuous problems. As before, our goal is to understand how this implies certificates of expansion.
We are talking about the sparsest cut of a graph , which is
We have looked for a while at the eigenvalues gap of . If is -regular and the second largest eigenvalue of is , then the difference between largest and second largest eigenvalue obeys
and, noting that when , we saw that is a relaxation of , and .
Leighton and Rao derive a continuous relaxation of in quite a different way. They note that when , then the “distance”
induces a semi-metric on , that is, , , and the triangle inequality holds
One can then consider the relaxation
where the minimum is taken over all distance functions that define a semi-metric on .
We can rewrite (1) as the linear program
where we only write the triangle inequality constraints by having one variable for every unordered pair .
The minimum of (2) gives a lower bound to the sparsest cut of , and so every feasible solution for the dual of (2) gives a lower bound to .
Before trying to write down the dual of (2), it is convenient to write (2) in a less efficient way. (This is akin to the fact that sometimes, when using induction, it is easier to prove a more general statement.) Instead of writing the triangle inequality for every three vertices, we write it for every arbitrary sequence of vertices.
where we denote by the set of “paths” in the complete graph between and . (That is, is the set of all sequences of vertices that start at and end at .)
Clearly (3) is the same as (2), in the sense that the extra inequalities present in (3) are implied by the triangle inequalities in (2). The dual of (3), however, is cleaner, and is given below
A feasible solution to (4) is thus a weighted set of paths and a parameter . Before reasoning about the meaning of a solution, suppose that satisfy the stronger constraints
Then we can view the as defining a flow between that carries at least units of flow; furthermore, the union of all such flows uses at most a total capacity on each edge . We should think of it as an embedding of the complete graph scaled by into . I want to claim that this means that the sparsest cut of is at least times the sparsest cut of the complete graph, that is, at least .
To verify the claim, take any cut . We know that such a cut separates pairs of vertices , and that at least units of flow are routed between each such pair, so that at least units of flow cross the cut. Since every edge has capacity 1, we see that at least edges of must cross the cut.
It remains to bridge the difference between (4) or (5). One possibility is to show that a solution to (4) can be modified to a solution satisfying (5) with no loss in . Another approach is to directly use (4) and a general weak duality argument to show directly that a solution satisfying (4) implies that has at least the edge expansion of a complete graph with edge weights .
There is, in fact, a broader principle at work, which we can verify by a similar argument: if is an assignment of weights to all possible paths (which we think of as defining a multicommodity flow), is a graph with adjacency matrix , is a graph with adjacency matrix , and we have
then we must have .
The fact that a feasible solution to (4) gives a lower bound to is a special case that applies to the case in which is a scaled version of the complete graph.
This is a good point to pause, look back again at the bound coming from spectral considerations, and compare it with what we have here. Continue reading