Arnold Filtser: Clan Embeddings into Trees, and Low Treewidth Graphs

Arnold FiltserBar-Ilan University
SHARE:
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 $\chi(x)\in f(x)$. The clan embedding has multiplicative distortion $t$ if for every pair $(x,y)$ some copy $y'\in f(y)$ in the clan of $y$ is  close to the chief of $x$$\min_{y'\in f(y)}d(y',\chi(x))\le t\cdot d(x,y)$. Our first result is a clan embedding into a tree with multiplicative distortion $O(\frac{\log n}{\epsilon})$ such that each point has $1+\epsilon$ 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 parameterized by $D$, which were known to be stochastically embeddable into bounded treewidth graphs with expected additive distortion $\epsilon 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 $\rho$-dominating set and metric $\rho$-independent set problems in minor-free graphs.

Joint work with Hung Le

Greg Bodwin

Euiwoong Lee