In which we prove that there are -point metric spaces that cannot be embedded into L1 with distortion
, and we see further applications of Leighton-Rao type relaxations and of the use of metric embeddings as rounding schemes.
1. Tightness of the Analysis of the Leighton-Rao Relaxation
If and
are metric spaces, we say that a mapping
is an embedding of
into
with distortion at most
if there are parameters
, with
such that, for every
, we have
The metric space with distance
is denoted by
, and the metric space
with distance
is denoted by
. In the past lecture we proved the following result.
Theorem 1 (Bourgain) There is an absolute constant
such that every finite metric space
embeds into
with distortion at most
, where
.
If we solve the Leighton-Rao linear programming relaxation to approximate the sparsest cut of a graph , and we let
be an optimal solution, we note that, if we weigh each edge
by
, and then compute shortest paths in this weighted graph, then, for every two vertices
, the distance
is precisely the length of the shortest path from
to
. In particular, if we are using the Leighton-Rao relaxation in order to approximate the sparsest cut in a given planar graph, for example, then the solution
that we need to round is not an arbitrary metric space, but it is the shortest path metric of a weighted planar graph. It is conjectured that, in this case, the Leighton-Rao relaxation could deliver a constant-factor approximation.
Is there an absolute constant such that every metric space
constructed as the shortest-path metric over the vertices of a planar graph can be embedded into
with distortion at most
, where
?
So far, it is known that –outerplanar graphs, for constant
, embed in
with constant distortion.
This is just an example of a large family of questions that can be asked about the embeddability of various types of metric spaces into each other.
For general finite metric spaces, the logarithmic distortion of Bougain’s theorem is best possible.
In order to prove the optimality of Bourgain’s theorem, we will state without proof the existence of constant degree families of expanders. In a later part of the course we will prove their existence and give efficient constructions.
Theorem 2 (Existence of Expanders) There are absolute constants
and
such that, for infinitely many
, there is an
-vertex
-regular graph
such that
.
On such graphs, the Leighton-Rao relaxation is , showing that our proof that
is tight.
For every two vertices , define
as the length of (that is, the number of edges in) a shortest path from
to
in
.
Then
Because each graph is
-regular, it follows that for every vertex
there are
vertices at distance
from
. In particular, at least half of the vertices have distance
from
, where
, which implies that
Recall that
and so
even though
Note that we have also shown that every embedding of the shortest-path metric on
into
requires distortion
, and so we have proved the tightness of Bourgain’s theorem.
2. The Non-Uniform Sparsest Cut Problem
In the non-uniform sparsest cut problem, we are given two graphs and
over the same set of vertices, and we want to find a non-trivial cut
of the vertex set that minimizes the non-uniformity sparsity
The non-uniformity sparsity of an optimal solution is denoted by . Note that the standard sparsest cut problem corresponds to taking
to be a clique.
The graph is called the capacity graph and the graph
is called the demand graph. This terminology will become more clear when we discuss the dual of the Leighton-Rao relaxation of sparsest cut at a later point. The intuition for the problem is that
specifies which pairs of nodes we would like to see disconnected in
, and our goal is to find a set of edges to remove such that their number is small compared to the number of pairs of elements of
that are disconnected by their removal.
We can easily adapt the theory that we have developed for sparsest cut to the non-uniform version of the problem. In particular, we can define a Leighton-Rao relaxation
where is the adjacency matrix of
and
is the adjacency matrix of
.
We can also define the special case of the Leighton-Rao relaxation in which the distance function is an embedding:
Exactly the same proof that established can be used to prove
And, finally, Bourgain’s embedding can be used to map a solution of the Leighton-Rao relaxation to an solution, with
increase in the cost function, and then the
solution can be mapped to a cut with no loss, leading to the relation
for every two graphs over the same set of vertices.
Prof. Trevisan, the sparsest cut problem seems to be “easier” in d-regular graph. Is the problem still NP-hard in d-regular graph?