Clan embeddings into trees, and low treewidth graphs

In low distortion metric embeddings, the goal is to embed a host "hard" metric space into a "simpler" target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric. Unfortunately, such embedding will result in a huge distortion. A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey-type embedding, where the distortion guarantee applies only to a subset of the points. However, both these solutions fail to provide an embedding into a single tree with a worst-case distortion guarantee on all pairs. In this paper, we propose a novel third bypass called clan embedding. Here each point x is mapped to a subset of points f (x), called a clan, with a special chief point χ(x) ∈ f (x). The clan embedding has multiplicative distortion t if for every pair (x, y) some copy y ′ ∈ f (y) in the clan of y is close to the chief of x: min y ′ ∈f (y) d(y ′ , χ(x)) ≤ t ⋅ d(x, y). Our first result is a clan embedding into a tree with multiplicative distortion O( log n ) such that each point has 1 + copies (in expectation). In addition, we provide a "spanning" version of this theorem for graphs and use it to devise the first compact routing scheme with constant size routing tables. We then focus on minor-free graphs of diameter prameterized by D, which were known to be stochastically embeddable into bounded treewidth graphs with expected additive distortion D. We devise Ramsey-type embedding and clan embedding analogs of the stochastic embedding. We use these embeddings to construct the first (bicriteria quasi-polynomial time) approximation scheme for the metric ρ-dominating set and metric ρ-independent set problems in minor-free graphs.