Algorithms For Low-Distortion Embeddings Into Geometrically Restricted Spaces

We study the problem of finding a minimum-distortion embedding of the shortest path metric of a weighted or unweighted graph into a "simpler" metric X. Computing such an embedding (exactly or approximately) is a non-trivial task even when X is the metric induced by a path, or, equivalently, the real line.

Embeddings of various metric spaces are frequently used in the design of algorithms, and a large literature has been developed around this study. Embeddings into 1- and 2-dimensional spaces can provide a natural abstraction of visualization tasks. Low-distortion embeddings into low-dimensional spaces can be used as a sparse representation of a data set, and embeddings into topologically restricted spaces can reveal interesting structures in a data set.

In general, unless P=NP many embedding problems cannot have algorithms which run in polynomial time. We work around this by finding approximation and fixed-parameter tractable (FPT) algorithms for minimum distortion embeddings of the shortest path metric of a graph G into the shortest path metric of a subdivision of some fixed graph H, or, equivalently, into any fixed 1-dimensional simplicial complex. More precisely, we study the following problem: For given graphs G, H and integer c, is it possible to embed G with distortion c into a graph homeomorphic to H? Under this formulation, embedding into the line is the special case H=K₂, and embedding into the cycle is the case H=K₃, where K_k denotes the complete graph on k vertices.

For this problem we give an approximation algorithm on unweighted G, which in time f(H)poly(n), for some function f, either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion poly(c). For the case of embedding into a cycle, we find a O(c⁴)-embedding of G in time O(cn³). We also give an exact FPT algorithm on G with maximum edge weight W, which in time f'(H, c, W)poly(n), for some function f', either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion c. For the case of embedding into a cycle, we find the embedding in time n⁴ c^O(cW).

Prior to our work, poly(OPT)-approximation or FPT algorithms were known only for embedding into paths and trees of bounded degrees.