$\Psi$. In the tree decomposition of $H$ to be constructed, the set $\Psi$
will belong to all the bags (with edges towards all the vertices). Thus we can
assume that $G^{\prime}$ is connected, since otherwise, we can simply solve
the problem on each connected component separately and combine the solutions
by taking the union of all graphs/embeddings.

Let $r\in G^{\prime}$ be an arbitrary vertex. For
$\sigma\in\left\\{1,\dots,\frac{5}{\delta}\right\\}$ set
$\mathcal{I}_{-1,\sigma}=[0,\sigma]$,
$\mathcal{I}_{-1,\sigma}^{+}=[0,\sigma+1]$, and

$\mbox{for $j\geq 0$,
set}\qquad\mathcal{I}_{j,\sigma}=\left[\frac{5j}{\delta}+\sigma,\frac{5(j+1)}{\delta}+\sigma\right),\quad\mbox{and}\quad\mathcal{I}_{j,\sigma}^{+}=\left[\frac{5j}{\delta}+\sigma-1,\frac{5(j+1)}{\delta}+\sigma+1\right),$

Set $U_{j,\sigma}=\left\\{v\in G^{\prime}\mid
d_{G^{\prime}}(r,v)\in\mathcal{I}_{j,\sigma}\right\\}$ and similarly
$U_{j,\sigma}^{+}$ w.r.t. $I_{j,\sigma}^{+}$. Let $G_{j,\sigma}$ be the graph
induced by $U^{+}_{j,\sigma}$, plus the vertex $r$. In addition, for every
vertex $v\in U^{+}_{j,\sigma}$ who has a neighbor in
$\cup_{j^{\prime}<j}U^{+}_{j^{\prime},\sigma}\setminus U_{j,\sigma}^{+}$, we
add an edge to $r$ of weight $d_{G}(v,r)$. Equivalently, $G_{j,\sigma}$ can be
constructed by taking the graph induced by $\cup_{j^{\prime}\leq
j}U^{+}_{j^{\prime},\sigma}$, and contracting all the internal edges out of
$U_{j,\sigma}^{+}$ into $r$. See Figure 4 (in Section 7) for an illustration.
Note that all the edges towards $r$ have weight at most $D=1$, thus
$G_{j,\sigma}$ is a nearly $h$-embedded graph with diameter at most
$2\cdot(\frac{5}{\delta}+3)=O(\frac{1}{\delta})$ and no apices.

Fix some $\sigma$ and $j$. Using Lemma 1 with parameter
$\Theta(\epsilon\cdot\delta)$, we construct a one-to-many embedding
$f_{j,\sigma}$, of $G_{j,\sigma}$ into a graph $H_{j,\sigma}$ with treewidth
$O_{h}(\frac{\log n}{\epsilon\cdot\delta})$, such that $f_{j,\sigma}$ is
clique preserving and has additive distortion
$\Theta(\epsilon\cdot\delta)\cdot O(\frac{1}{\delta})=\epsilon$. After the
application of Lemma 1, we will merge all copies of $r$, and add edges from
$r$ to all the other vertices (where the weight of a new edge
$\left(r,v\right)$ is $d_{G}(r,v)$). Note that this increases the treewidth by
at most $1$. Furthermore, we will assume that there is a bag containing only
the vertex $r$ (as we can simply add such a bag). Next, fix $\sigma$. Let
$H^{\prime}_{\sigma}$ be a union of the graphs $\cup_{j\geq-1}H_{j,\sigma}$.
We identify the vertex $r$ with itself, but for all the other vertices that
participate in more than one graph, their copies in each graph remain
separate. Formally, we define a one-to-many embedding $f_{\sigma}$, where
$f_{\sigma}(r)$ equals to the unique $r$, and for every other vertex $v\in
V\setminus\Psi$, $f_{\sigma}(v)=\bigcup_{j\geq-1}f_{j,\sigma}(v)$. Note that
$H^{\prime}_{\sigma}$ has a tree decomposition of width $O_{h}(\frac{\log
n}{\epsilon\cdot\delta})$, by identifying the bag containing only $r$ in all
the graphs. Finally, we create the graph $H_{\sigma}$ by adding the set $\Psi$
with edges towards all the vertices in $H^{\prime}_{\sigma}$, where the weight
of a new edge $\left(u^{\prime},v\right)$ is $d_{G}(u,v)$. For $v\in\Psi$, set
$f_{\sigma}(v)=\\{v\\}$. As $\Psi=O_{h}(1)$, $H_{\sigma}$ has treewidth
$O_{h}(\frac{\log n}{\epsilon\cdot\delta})$. Finally, set
$M_{j,\sigma}=\left\\{v\in G^{\prime}\mid
d_{G^{\prime}}(r,v)\in\big{[}\frac{5j}{\delta}+\sigma+2,\frac{5(j+1)}{\delta}+\sigma-2\big{)}\right\\}$
, and $M_{\sigma}=\Psi\cup\\{r\\}\cup\bigcup_{j\geq-1}M_{j,\sigma}$. This
finishes the construction.

Observe that the one-to-many embedding $f_{\sigma}$ is dominating. This
follows from the triangle inequality since every edge
$\\{u^{\prime},v^{\prime}\\}$ for $u^{\prime}\in f_{\sigma}(u),v^{\prime}\in
f_{\sigma}(v)$ in the graph has weight $d_{G}(u,v)$. Next we argue that
$f_{\sigma}$ is clique-preserving. Consider a clique $Q$ in $G$, and let
$\tilde{Q}=Q\setminus\Psi$ be the non apex vertices in $Q$. We will show that
$f_{\sigma}$ contains a clique copy of $\tilde{Q}$. As the apices have edges
towards all the other vertices, it will imply that $f_{\sigma}$ is clique-
preserving. Let $v\in\tilde{Q}$ be some arbitrary vertex, and $j$ be the
unique index such that $v\in U_{j,\sigma}$. For every $u\in\tilde{Q}$,
$d_{G^{\prime}}(v,u)=d_{G}(v,u)\leq 1$, implying $u\in U^{+}_{j,\sigma}$. We
conclude that all $\tilde{Q}$ vertices belong to $G_{j,\sigma}$. As
$f_{j,\sigma}$ is clique-preserving, it follows that there is a bag in
$H_{j,\sigma}$, and thus also in $H_{\sigma}$, containing a clique copy of
$\tilde{Q}$.

Next, we argue that property (1) holds. We say that $f$ fails on a vertex
$v\in V$ if $v\notin M$, and we say that $f$ fails on a clique $Q$ if
$Q\nsubseteq M$. Consider some clique $Q$; we can assume w.l.o.g. that $Q$
does not contain any apex vertices (as $f$ never fails on an apex vertex). Let
$s_{Q},t_{Q}\in Q$ be the closest and farthest vertices from $r$ in
$G^{\prime}$, respectively. Then
$d_{G^{\prime}}(r,t_{Q})-d_{G^{\prime}}(r,s_{Q})\leq
d_{G^{\prime}}(s_{Q},t_{Q})\leq 1$. $f_{\sigma}$ fails on $Q$ iff there is a
non-empty intersection between the interval
$[d_{G^{\prime}}(r,t_{Q}),d_{G^{\prime}}(r,s_{Q}))$ and the interval
$[\frac{5j}{\delta}+\sigma-2,\frac{5j}{\delta}+\sigma+2)$ for some $j$. Note
that there are at most $5$ values of $\sigma$ for which this intersection is
non-empty. As we constructed $q=\frac{5}{\delta}$ embeddings,

$\Pr_{\sigma}\left[Q\subseteq
M_{\sigma}\right]=\frac{\left|\left\\{\sigma\in[q]\mid Q\subseteq
M_{\sigma}\right\\}\right|}{q}\geq\frac{q-5}{q}=1-\delta$

Finally, we show that $f_{\sigma}$ has additive distortion $\epsilon D$ w.r.t.
$M_{\sigma}$. Consider a pair of vertices $u\in M_{\sigma}$ and $v\in V$. If
one of $u,v$ belongs to $\Psi\cup\\{r\\}$ then for every $u^{\prime}\in
f_{\sigma}(u)$ and $v^{\prime}\in f_{\sigma}(v)$,
$d_{H_{\sigma}}(u^{\prime},v^{\prime})=d_{G}(u,v)$. Otherwise, if
$d_{G^{\prime}}(u,v)>d_{G}(u,v)$, then it must be that the shortest path
between $u$ to $v$ in $G$ goes through an apex vertex $z\in\Psi$. In
$H_{\sigma}$, $f_{\sigma}(z)$ is a singleton that have an edge towards every
other vertex. It follows that $\max_{u^{\prime}\in f_{\sigma}(u),v^{\prime}\in
f_{\sigma}(v)}d_{H_{\sigma}}(u^{\prime},v^{\prime})\leq\max_{u^{\prime}\in
f_{\sigma}(u),v^{\prime}\in
f_{\sigma}(v)}d_{H_{\sigma}}(u^{\prime},f_{\sigma}(z))+d_{H_{\sigma}}(f_{\sigma}(z),v^{\prime})=d_{G}(u,z)+d_{G}(z,v)=d_{G}(u,v)\leavevmode\nobreak\
.$

Else, $d_{G^{\prime}}(u,v)=d_{G}(u,v)\leq D=1$. Let $j$ be the unique index
such that $u\in U_{j,\sigma}$. As $u\in M_{j,\sigma}$, it implies that there
is no index $j^{\prime}\neq j$ such that $v\in U^{+}_{j^{\prime},\sigma}$. In
particular, all the vertices in the shortest path between $u$ to $v$ in $G$
are in $U_{j,\sigma}$. Thus, we have

$\max_{u^{\prime}\in f_{\sigma}(u),v^{\prime}\in
f_{\sigma}(v)}d_{H_{\sigma}}(u^{\prime},v^{\prime})\leq\max_{u^{\prime}\in
f_{j,\sigma}(u),v^{\prime}\in
f_{j,\sigma}(v)}d_{H_{j,\sigma}}(u^{\prime},v^{\prime})\leq
d_{G_{j,\sigma}}(u,v)+\epsilon D=d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ ,$

as desired. ∎

Consider a $K_{r}$-minor-free graph $G$, and let $\mathbb{T}$ be its clique-
sum decomposition. That is $G=\cup_{(G_{i},G_{j})\in
E(\mathbb{T})}G_{i}\oplus_{h(r)}G_{j}$ where each $G_{i}$ is a nearly
$h(r)$-embeddable graph. We call the clique involved in the clique-sum of
$G_{i}$ and $G_{j}$ the _joint set_ of the two graphs. Here $h(r)$ is a
function depending on $r$ only. Let $\phi_{h}$ be some function depending only
on $h$ such that the treewidth of the graphs constructed in Lemma 15 is
bounded by $\phi_{h}\cdot\frac{\log n}{\epsilon\cdot\delta}$.

The embedding of $G$ is defined recursively, where some vertices from former
levels will be added to future levels as apices. In order to control the
number of such apices, we will use the following concept.

######  Definition 9 (Enhanced minor-free graph).

A graph $G$ is called $(r,s,t)$_-enhanced minor free graph_ if there is a set
$S$ of at most $s$ vertices, called elevated vertices, such that every
elevated vertex $u\in S$ has edges towards all the other vertices and
$G\setminus S$ is a $K_{r}$-minor-free graph that has a clique-sum
decomposition with $t$ pieces.

We will prove the following claim by induction on $t$:

######  Lemma 16.

Given an $n$-vertex $(r,s,t)$-enhanced minor-free graph $G$ of diameter $D$
with a set $S$ of elevated vertices, and parameter
$\epsilon\in(0,\frac{1}{4})$, there is a distribution over one-to-many,
clique-preserving, dominating embeddings $f$ into graphs $H$ of treewidth
$\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta}+s+h(r)\cdot\log t$, such
that there is a subset $M\subseteq V$ of vertices for which the following
hold:

  1. 1.

For every $v\in V$, $\Pr[v\in M]\geq 1-\delta\cdot\log 2t$.

  2. 2.

For every $u\in M$ and $v\in V$, $\max_{u^{\prime}\in f(u),v^{\prime}\in
f(v)}d_{H_{\sigma}}(u^{\prime},v^{\prime})\leq d_{G}(u,v)+\epsilon D$.

W now show that Lemma 16 implies Theorem 4:

###### Proof of Theorem 4.

Note that every $K_{r}$-minor-free graph is $(r,0,n)$-enhanced minor free.
Apply Lemma 16 using parameters $\epsilon$ and
$\delta^{\prime}=\frac{\delta}{\log 2n}$ to obtain a distribution of
embeddings. For each embedding $f$ in the distribution, define another
embedding $g$ by setting $g(v)$ for each $v\in V$ to be an arbitrary vertex
from $f(v)$. We obtain a distribution over embeddings into treewidth
$\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta^{\prime}}+0+h(r)\cdot\log
n=O_{r}(\frac{\log^{2}n}{\epsilon\delta})$ graphs with distortion $\epsilon
D$, such that for every vertex $v\in V$, $\Pr[v\in M]\geq
1-\delta^{\prime}\cdot\log 2n=1-\delta$. ∎

###### Proof of Lemma 16.

It follows from Lemma 15 that the claim holds for the base case $t=1$. We now
turn to the induction step. Consider an $(r,s,t)$-enhanced minor-free graph
$G$. Let $G^{\prime}$ be a $K_{r}$-minor-free graph obtained from $G$ by
removing a set $S$ of elevated vertices. Let $\mathbb{T}$ be the clique-sum
decomposition of $G^{\prime}$ with $t$ pieces. We use the following lemma to
pick a central piece $\mathcal{G}$ of $\mathbb{T}$.

######  Lemma 17 ([Jor69]).

Given a tree $T$ of $n$ vertices, there is a vertex $v$ such that every
connected component of $T\setminus\\{v\\}$ has at most $\frac{n}{2}$ vertices.

Let $G_{1},\dots,G_{p}$ be the neighbors of $\tilde{G}$ in $\mathbb{T}$. Note
that $\mathbb{T}\setminus\tilde{G}$ contains $p$ connected components
$\mathbb{T}_{1},\dots,\mathbb{T}_{p}$, where $G_{i}\in\mathbb{T}_{i}$, and
$\mathbb{T}_{i}$ contains at most $|\mathbb{T}|/2=t/2$ pieces. Let $Q_{i}$ be
the clique used in the clique-sum of $G_{i}$ with $\tilde{G}$ in $\mathbb{T}$.
For every $i$, we will add edges between $Q_{i}$ vertices to all the vertices
in $\mathbb{T}_{i}$. That is, we add $Q_{i}$ to the set of elevated vertices
in the graph induced by pieces in $\mathbb{T}_{i}$. Every new edge $\\{u,v\\}$
will have the weight $d_{G}(u,v)$. Let $\mathcal{G}_{i}$ be the graph induced
on vertices of $\mathbb{T}_{i}\cup S$ (and the newly added edges). Note that
$\mathcal{G}_{i}$ is an $(r,s^{\prime},t^{\prime})$-enhanced minor-free graph
for $t^{\prime}\leq\frac{t}{2}$ and $|s^{\prime}|\leq|S|+|Q_{i}|\leq s+h(r)$.
Furthermore, for every $u,v\in\mathcal{G}_{i}$, it holds that
$d_{\mathcal{G}_{i}}(u,v)=d_{G}(u,v)$. Thus, each $\mathcal{G}_{i}$ has
diameter at most $D$. Using the inductive hypothesis on $\mathcal{G}_{i}$, we
sample a dominating embedding $f_{i}$ into $H_{i}$, and a subset
$M_{i}\subseteq\mathcal{G}_{i}$ of vertices. Note that properties (1)-(2)
hold, and $H_{i}$ has treewidth $\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s^{\prime}+h(r)\cdot\log
2t^{\prime}\leq\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s+h(r)\cdot\log 2t$.

Let $\tilde{\mathcal{G}}$ be the graph induced on $\tilde{G}\cup S$. Note that
$\tilde{\mathcal{G}}$ has diameter at most $D$. We apply Lemma 15 to
$\tilde{\mathcal{G}}$ to sample a dominating embedding $\tilde{f}$ into
$\tilde{H}$, and a subset $\tilde{M}$ of vertices. Note that properties
(1)-(2) hold, in particular, the treewidth of $\tilde{H}$ is bounded by
$\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta}+s$ (as the construction
first will delete the elevated vertices and eventually add them to all the
bags).

As the embeddings $\tilde{f},f_{1},\dots,f_{p}$ are clique-preserving
embeddings into $\tilde{H},H_{1},\dots,H_{p}$, there is a natural way to
combine them into a single graph $H$ of treewidth $\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s+h(r)\cdot\log 2t$. In more detail, initially, we
just take a disjoint union of all the graphs $\tilde{H},H_{1},\dots,H_{p}$,
keeping all copies of the different vertices separately. Next, we identify all
the copies of the elevated vertices. Finally, for each $i$, as both
$\tilde{f}$ and $f_{i}$ are clique-preserving, we simply take two clique
copies of $Q_{i}$ from $\tilde{f}$ and $f_{i}$, and identify the respective
vertices in this two clique copies. Note that every vertex $v\in Q_{i}$ is an
elevated vertex in $\mathcal{G}_{i}$, and thus $f_{i}(v)$ is unique. The
embedding $f$ is defined as follows: For $v\in\tilde{\mathcal{G}}$, set
$f(v)=\tilde{f}(v)$, while for
$v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$ for some $i$, set
$f(v)=f_{i}(v)$.

We now define the subset $M\subseteq V$. Every vertex $v\in\tilde{M}$ joins
$M$. A vertex $v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$ join $M$ if
and only if $v\in M_{i}$ and $Q_{i}\subseteq\tilde{M}$. Note that for vertices
in $\tilde{\mathcal{G}}$, property (1) holds trivially, while for
$v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$, using the induction
hypothesis and union bound

$\Pr\left[v\notin M\right]\leq\Pr\left[v\notin
M_{i}\right]+\Pr\left[Q_{i}\nsubseteq\tilde{M}\right]\leq\delta\cdot\log
2t^{\prime}+\delta\leq\delta\cdot\log 2t\leavevmode\nobreak\ .$

Hence property (1) holds. Note that $f$ is clique-preserving as every clique
must be contained in either $\tilde{\mathcal{G}}$ or some $\mathcal{G}_{i}$.
Finally, we show that property (2) holds. Consider a vertex $u\in M$ and $v\in
V$. We proceed by case analysis.

  * •

If a shortest path from $u$ to $v$ goes through a vertex $z\in S$ (this
includes the case where either $u$ or $v$ is in $S$). Then for every
$u^{\prime}\in f(u)$ and $v^{\prime}\in f(v)$, it holds that
$d_{H}(u^{\prime},v^{\prime})\leq
d_{H}(u^{\prime},f(z))+d_{H}(f(z),v^{\prime})=d_{G}(u,z)+d_{G}(z,v)=d_{G}(u,v)$.

  * •

Else, if both $u,v\in\tilde{G}$, then by Lemma 15, $\max_{u^{\prime}\in
f(u),v^{\prime}\in
f(v)}d_{H}(u^{\prime},v^{\prime})\leq\max_{u^{\prime}\in\tilde{f}(u),v^{\prime}\in\tilde{f}(v)}d_{\tilde{H}}(u^{\prime},v^{\prime})\leq
d_{\mathcal{\tilde{G}}}(u,v)+\epsilon D=d_{G}(u,v)+\epsilon D$.

  * •

Else, if there is an $i\in[p]$ such that both
$u,v\in\mathcal{G}_{i}\setminus\tilde{G}$, then by the induction hypothesis
$\max_{u^{\prime}\in f(u),v^{\prime}\in
f(v)}d_{H}(u^{\prime},v^{\prime})\leq\max_{u^{\prime}\in
f_{i}(u),v^{\prime}\in f_{i}(v)}d_{H_{i}}(u^{\prime},v^{\prime})\leq
d_{\mathcal{G}_{i}}(u,v)+\epsilon D=d_{G}(u,v)+\epsilon D$.

  * •

Else, if $u\in\tilde{G}$ and there is an $i\in[p]$ such that
$v\in\mathcal{G}_{i}$. There is necessarily a vertex $x\in Q_{i}$ such that
there is a shortest path from $u$ to $v$ in $G$ going through $x$. Let
$\hat{x}$ be the copy of $x$ used to connect between $\tilde{H}$ and $H_{i}$.
Note that there is an edge between $\hat{x}$ to every copy $v^{\prime}\in
f_{i}(v)$ in $H_{i}$. In addition, as $u\in\tilde{M}$, by the second case it
holds that $\max_{u^{\prime}\in
f(u)}d_{H}(u^{\prime},\hat{x})\leq\max_{u^{\prime}\in f(u),x^{\prime}\in
f(x)}d_{H}(u^{\prime},\hat{x})\leq d_{G}(u,x)+\epsilon D$. We conclude

$\displaystyle\max_{u^{\prime}\in f(u),v^{\prime}\in
f(v)}d_{H}(u^{\prime},v^{\prime})$ $\displaystyle\leq\max_{u^{\prime}\in
f(u)}d_{H}(u^{\prime},\hat{x})+\max_{v^{\prime}\in
f(v)}d_{H}(\hat{x},v^{\prime})$ $\displaystyle\leq d_{G}(u,x)+\epsilon
D+d_{G}(x,v)=d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$ (5)

  * •

Else, if $v\in\tilde{G}$ and there is an $i\in[p]$ such that
$u\in\mathcal{G}_{i}\setminus\tilde{G}$. There is necessarily a vertex $x\in
Q_{i}$ such that there is a shortest path from $u$ to $v$ in $G$ going through
$x$. As $u\in M$ it follows that $x\in\tilde{M}\subseteq M$. Let $\hat{x}$ be
the copy of $x$ used to connect between $\tilde{H}$ and $H_{i}$; we observe
that inequality (5) holds in this case.

  * •

Else, there are $i\neq j$ such that $u\in\mathcal{G}_{i}\setminus\tilde{G}$
and $v\in\mathcal{G}_{j}\setminus\tilde{G}$. There is necessarily a vertex
$x\in Q_{i}$ such that there is a shortest path from $u$ to $v$ in $G$ going
through $x$. As $u\in M$ it follows that $x\in\tilde{M}\subseteq M$. Let
$\hat{x}$ be the copy of $x$ used to connect between $\tilde{H}$ and $H_{i}$.
By the forth case, it holds that $\max_{x^{\prime}\in f(x),v^{\prime}\in
f(v)}d_{H}(x^{\prime},v^{\prime})\leq d_{G}(x,v)+\epsilon D$. Thus,

$\displaystyle\max_{u^{\prime}\in f(u),v^{\prime}\in
f(v)}d_{H}(u^{\prime},v^{\prime})$ $\displaystyle\leq\max_{u^{\prime}\in
f(u)}d_{H}(u^{\prime},\hat{x})+\max_{v^{\prime}\in
f(v)}d_{H}(\hat{x},v^{\prime})$ $\displaystyle\leq
d_{G}(u,x)+d_{G}(x,v)+\epsilon D=d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$

∎

##  7 Clan Embedding for Minor-Free Graphs

This section is devoted to proving Theorem 5 (restated below for convenience).
The proof of Theorem 5 builds upon a similar approach to Theorem 4, however,
it is more delicate and considerably more involved. We present the proof here
without assuming familiarity with the proof of Theorem 4. Nonetheless, we
recommend the reader to first understand the proof of Theorem 4 before reading
this section. See 5

######  Remark 3.

Note that Theorem 5 implies a weak version Theorem 4, where the distortion
guarantee is for pairs $u,v\in M$ rather than than for $u\in M$ and $v\in V$:
simply use the chief part $\chi$ as a Ramsey type embedding and set
$M=\\{v\mid|f(v)|=1\\}$. Interestingly, this weaker version is still
sufficient for our application to the metric $\rho$-independent set problem
(Theorem 7).

We begin with Lemma 18, which is a special case of nearly-embeddable graphs.
Later, we will generalize to minor-free graphs via clique-sums. Specifically,
inductively we will use Lemma 18 for each piece, and integrate it to the
general embedding. However, for this integration to go through, we will need
the intermediate embedding to be clique-preserving. As a consequence, we will
not attempt to bound the size of $f$ directly. Instead, for every vertex $v$,
$f(v)$ will be the union of two sets $\chi(v)$ and $\psi(v)$. Eventually, for
the clan embedding, we will take _one copy from each set_. We will say that
the embedding succeeds on a vertex $v$ if $\psi(v)=\emptyset$. (In the
following lemma, $\bigcupdot$ denotes the disjoint-union operation.)

######  Lemma 18.

Consider a nearly $h$-embeddable $n$-vertex graph $G=(V,E,w)$ with set of
apices $\Psi$, diameter $D$, and parameters $\epsilon\in(0,\frac{1}{4})$,
$\delta\in(0,1)$. Then there is a distribution over one-to-many, dominating
embeddings $f$ into treewidth $O_{h}(\frac{\log n}{\epsilon\delta})$ graphs,
such that for every vertex $v\in V$, $f(v)$ can be partitioned into sets
$\chi(v),\psi(v)$ where $\chi(v)\bigcupdot\psi(v)=f(v)$.It holds that:

  1. 1.

For every pair of vertices $u,v$, 131313Note that $\psi(v)$ might be an empty
set. A maximum over an empty set is defined to be $\infty$.

$\min\left\\{\max_{u^{\prime}\in\chi(u),v^{\prime}\in\chi(v)}d_{H}(u^{\prime},v^{\prime}),\max_{u^{\prime}\in\psi(u),v^{\prime}\in\chi(v)}d_{H}(v^{\prime},u^{\prime})\right\\}\leq
d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$ (6)

  2. 2.

We say that $f$ fails on a vertex $v$ if $\psi(v)\neq\emptyset$. For a clique
$Q\subseteq V$, we say that $f$ fails on $Q$ if it fails on some vertex in
$Q$. For every clique $Q\subseteq V$, $\Pr[f\mbox{ fails on }Q]\leq\delta$.

  3. 3.

Consider a clique $Q$, one of the following holds:

    1. (a)

$f$ succeeds on $Q$. In particular $\chi(Q)$ contains a clique copy of $Q$.

    2. (b)

$f$ fails on $Q$, and $\chi(Q)$ contains a clique copy of $Q$. In addition,
consider the set
$Q^{F}=\\{v\in Q\mid\psi(v)\neq 0\\}$, then $\psi(Q^{F})$ contains a clique
copy of $Q^{F}$.

    3. (c)

$f$ fails on $Q$, and $f(Q)$ contains two cliques copies $Q^{1},Q^{2}$ of $Q$
such that for every vertex $v\in Q\setminus\Psi$, both $\chi(v)\cap(Q^{1}\cup
Q^{2})$ and $\psi(v)\cap(Q^{1}\cup Q^{2})$ are singletons. In this case, in
addition to equation (6), it also holds that for every $u\in V$ and $v\in
Q\setminus\Psi$,

$\min\left\\{\max_{u^{\prime}\in\chi(u),v^{\prime}\in\psi(v)}d_{H}(u^{\prime},v^{\prime}),\max_{u^{\prime}\in\psi(u),v^{\prime}\in\psi(v)}d_{H}(u^{\prime},v^{\prime})\right\\}\leq
d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$ (7)

###### Proof.

Consider a nearly $h$-embedded graph $G=(V,E,w)$. Assume w.l.o.g. that $D=1$,
otherwise we can scale accordingly. We assume that $1/\delta$ is an integer,
otherwise we solve for $\delta^{\prime}$ such that
$\frac{1}{\delta^{\prime}}=\lceil\frac{1}{\delta}\rceil$. We will construct
$q=\frac{8}{\delta}$ embeddings satisfying property (1) of Lemma 18. The final
embedding will be obtained by choosing one of these embeddings uniformly at
random. Denote by $G^{\prime}=G[V\setminus\Psi]$ the induced subgraph obtain
by removing the apices. In the tree decomposition of $H$ we will construct,
the set $\Psi$ will belong to all the bags (with edges towards all the
vertices). Thus we can assume that $G^{\prime}$ is connected, as otherwise we
can simply solve the problem on each connected component separately, and
combine the solutions by taking the union of all graphs/embeddings.

Let $r\in G^{\prime}$ be an arbitrary vertex. For
$\sigma\in\left\\{4,\dots,\frac{8}{\delta}\right\\}$, set
$\mathcal{I}_{-1,\sigma}=[0,\sigma]$,
$\mathcal{I}_{-1,\sigma}^{+}=[0,\sigma+2]$, and for $j\geq 0$, set
$\mathcal{I}_{j,\sigma}=\left[\frac{8j}{\delta}+\sigma,\frac{8(j+1)}{\delta}+\sigma\right)$,
and
$\mathcal{I}_{j,\sigma}^{+}=\left[\frac{8j}{\delta}+\sigma-2,\frac{8(j+1)}{\delta}+\sigma+2\right)$.
Set $U_{j,\sigma}=\left\\{v\in G^{\prime}\mid
d_{G^{\prime}}(r,v)\in\mathcal{I}_{j,\sigma}\right\\}$ and similarly
$U_{j,\sigma}^{+}$ w.r.t. $I_{j,\sigma}^{+}$. Note that by the triangle
inequality, for every pair of neighboring vertices $u,v$ it holds that
$d_{G}(u,v)\leq D=1$; thus, $u\in U_{j,\sigma}$ implies $v\in
U^{+}_{j,\sigma}$. Let $G_{j,\sigma}$ be the graph induced by
$U^{+}_{j,\sigma}$, plus the vertex $r$. In addition, we add edges from the
vertex $r$ towards all the vertices with neighbors in
$(\cup_{q<j}U^{+}_{q,\sigma})\setminus U^{+}_{j,\sigma}$ (where the weight of
a new edge $\left(r,v\right)$ is $d_{G}(r,v)$). Equivalently, $G_{j,\sigma}$
can be constructed by taking the graph induced by $\cup_{j^{\prime}\leq
j}U^{+}_{j^{\prime},\sigma}$ and contracting all the internal edges out of
$U_{j,\sigma}^{+}$ into $r$. Note that all the edges towards $r$ have weight
at most $D=1$. Furthermore, for every vertex $v\in G_{j,\sigma}$,
$d_{G_{j,\sigma}}(v,r)<1+\frac{8}{\delta}+4$. Thus $G_{j,\sigma}$ is a nearly
$h$-embedded graph with diameter at most
$\frac{16}{\delta}+10=O(\frac{1}{\delta})$ and no apices. See Figure 4 for an
illustration.

Figure 4: On the left is the graph $G^{\prime}$. $r$ is the big black vertex
in the middle. The dashed orange lines separate between the layers of
$U_{-1,\sigma},U_{0,\sigma},U_{1,\sigma},\dots$. The two blue lines are the
boundaries of $U^{+}_{0,\sigma}$. All the vertices in $U^{+}_{0,\sigma}$ (and
the edges between them) are black, while all other vertices (and the edges
incident on them) are gray. On the right is the graph $G_{0,\sigma}$ with
vertex set $U^{+}_{0,\sigma}\cup\\{r\\}$, where the edges added from $r$ to
vertices with neighbors in $U^{+}_{-1,\sigma}\setminus U^{+}_{0,\sigma}$ are
marked in red.

Fix some $\sigma$ and $j$. Using Lemma 1 with parameter
$\Theta(\epsilon\cdot\delta)$, we construct a dominating one-to-many embedding
$f_{j,\sigma}$, of $G_{j,\sigma}$ into a graph $H_{j,\sigma}$ with treewidth
$O_{h}(\frac{\log n}{\epsilon\cdot\delta})$, such that $f_{j,\sigma}$ is
clique preserving and has additive distortion
$\Theta(\epsilon\cdot\delta)\cdot O(\frac{1}{\delta})=\epsilon$. After the
application of Lemma 1, we will add edges from $r$ to all the other vertices
(where the weight of a new edge $\left(r,v\right)$ is $d_{G}(r,v)$). Note that
this increases the treewidth by at most $1$. Further, we will assume that
there is a bag containing only the vertex $r$ (as we can simply add such a
bag). Next, fix $\sigma$. Let $H^{\prime}_{\sigma}$ be a union of the graphs
$\cup_{j\geq-1}H_{j,\sigma}$. We identify the vertex $r$ with itself, but all
copies of other vertices that participate in more that a single graph will
remain separate. Formally, we define a one-to-many embedding $f_{\sigma}$,
where $f_{\sigma}(r)$ equals to the unique vertex $r$, and for every other
vertex $v\in V\setminus\Psi$,
$f_{\sigma}(v)=\bigcup_{j\geq-1}f_{j,\sigma}(v)$. Note that
$H^{\prime}_{\sigma}$ has a tree decomposition of width $O_{h}(\frac{\log
n}{\epsilon\cdot\delta})$, by identifying the bag containing only $r$ in all
the graphs. Finally, we create the graph $H_{\sigma}$ by adding the set $\Psi$
with edges towards all the vertices in $H^{\prime}_{\sigma}$, where the weight
of a new edge $\left(u^{\prime},v\right)$ for $u\in f_{\sigma}(u)$ and
$v\in\Psi$ is $d_{G}(u,v)$. For $v\in\Psi$, set $f_{\sigma}(v)=\\{v\\}$. As
$\Psi=O_{h}(1)$, $H_{\sigma}$ has treewidth $O_{h}(\frac{\log
n}{\epsilon\cdot\delta})$. The one-to-many embedding $f_{\sigma}$ is
dominating. This follows by the triangle inequality as every edge $\\{u,v\\}$
in the graph has weight $d_{G}(u,v)$. Finally, the embedding $f$ is chosen to
equal $f_{\sigma}$, for $\sigma$ chosen uniformly at random. This concludes
the definition of the embedding $f$.

Next, we define the partition $\chi_{\sigma}(v)\bigcupdot\psi_{\sigma}(v)$ of
$f_{\sigma}(v)$ for each vertex $v\in V$ as follows:

  * •

If $v\in\Psi\cup\\{r\\}$, then there is a single copy of $v$ in $f_{\sigma}$.
Set $\chi_{\sigma}(v)=f_{\sigma}(v)$ and $\psi_{\sigma}(v)=\emptyset$.

  * •

Else, let $j$ be the unique index such that $v\in U_{j,\sigma}$. Set
$\chi_{\sigma}(v)=f_{j,\sigma}(v)$. If there is another index $j^{\prime}$
such that $v\in U^{+}_{j^{\prime},\sigma}$, set
$\psi_{\sigma}(v)=f_{j^{\prime},\sigma}(v)$, otherwise set
$\psi_{\sigma}(v)=\emptyset$.

Clearly, as there are at most $2$ indices $j$ such that $v\in
U^{+}_{j,\sigma}$, $\chi_{\sigma}(v)\bigcupdot\psi_{\sigma}(v)=f_{\sigma}(v)$.

Next, we prove property (1)\- the stretch bound. Consider a pair of vertices
$u,v\in V$. If $v\in\Psi\cup\\{r\\}$ then $f_{\sigma}(v)$ is a singleton with
an edge towards every copy of $u$, thus property (1) holds. The same argument
holds also if $u\in\Psi\cup\\{r\\}$. Otherwise, if
$d_{G^{\prime}}(u,v)>d_{G}(u,v)$, then the shortest path between $u$ to $v$ in
$G$ goes through an apex vertex $z\in\Psi$. In particular, $f_{\sigma}(z)$ is
a singleton with an edge towards every other vertex. It follows that in
$H_{\sigma}$, the distance between every two copies in $f_{\sigma}(v)$ and
$f_{\sigma}(u)$ is exactly $d_{G}(u,z)+d_{G}(z,v)=d_{G}(u,v)$. Else,
$d_{G^{\prime}}(u,v)=d_{G}(u,v)$. Let $j$ be the unique index such that $v\in
U_{j,\sigma}$, then $u\in U^{+}_{j,\sigma}$. Furthermore,
$d_{G_{j,\sigma}}(u,v)=d_{G^{\prime}}(u,v)$ since the entire shortest path
between them is in $U^{+}_{j,\sigma}$. By Lemma 1,

$\displaystyle\min\left\\{\max_{u^{\prime}\in\chi_{\sigma}(u),v^{\prime}\in\chi_{\sigma}(v)}d_{H_{\sigma}}(u^{\prime},v^{\prime}),\max_{u^{\prime}\in\psi_{\sigma}(u),v^{\prime}\in\chi_{\sigma}(v)}d_{H_{\sigma}}(v^{\prime},u^{\prime})\right\\}$
$\displaystyle\qquad\leq\max_{u^{\prime}\in f_{j,\sigma}(u),v^{\prime}\in
f_{j,\sigma}(v)}d_{H_{j,\sigma}}(u^{\prime},v^{\prime})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ d_{G_{j,\sigma}}(u,v)+\epsilon D\leavevmode\nobreak\
=\leavevmode\nobreak\ d_{G^{\prime}}(u,v)+\epsilon D\leavevmode\nobreak\
=\leavevmode\nobreak\ d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$

Next we argue property (2)\- the failure probability of a clique. Recall that
$f,\chi,\psi$ will equal to $f_{\sigma},\chi_{\sigma},\psi_{\sigma}$ for
$\sigma\in\\{1,\dots,\frac{8}{\delta}\\}$ chosen uniformly at random. Consider
some clique $Q$, we can assume w.l.o.g. that $Q$ does not contain any apex
vertices (as $f$ never fails on apex vertex). Let $s_{Q},t_{Q}\in Q$ be the
closest and farthest vertices from $r$ in $G^{\prime}$, respectively. Then
$d_{G^{\prime}}(r,t_{Q})-d_{G^{\prime}}(r,s_{Q})\leq
d_{G^{\prime}}(s_{Q},t_{Q})\leq D=1$. $f_{\sigma}$ fails on $Q$ iff there is a
non-empty intersection between the interval
$[d_{G^{\prime}}(r,t_{Q}),d_{G^{\prime}}(r,s_{Q}))$ (of length at most $1$)
and interval $[\frac{8j}{\delta}+\sigma-2,\frac{8j}{\delta}+\sigma+2)$ for
some $j$. Note that there are at most $5$ choices of $\sigma$ on which this
happens. We conclude that $\Pr[f\mbox{ fails on
}Q]\leq\frac{5}{\nicefrac{{8}}{{\delta}}-3}\leq\delta$.

[capbesideposition=left,top,capbesidewidth=7.3cm]figure[]

Figure 5: Illustration of the different cases in property (3). The green area
marks all the vertices in $U^{+}_{j,\sigma}$. The vertices in $U_{j,\sigma}$
are enclosed between the two black semicircles. The vertices in
$U^{+}_{j,\sigma}\cap U^{+}_{j+1,\sigma}$ (resp. $U^{+}_{j-1,\sigma}\cap
U^{+}_{j,\sigma}$) are enclosed between the red (resp. orange) dashed
semicircles. In the first case (a), all the vertices of $Q$ are in
$U_{j,\sigma}$ and no vertex failed. In the second case (b), all the vertices
of $Q$ are in $U_{j,\sigma}$ and some vertices failed. In the third case (c),
the vertices of $Q$ non-trivially partitioned between $U_{j,\sigma}$ and
$U_{j+1,\sigma}$, and all of them failed.

Finally, we prove property (3)\- clique preservation. Consider a clique $Q$,
note that we can assume that $Q\subseteq G^{\prime}$, as $f_{\sigma}$ will not
fail on any apex. Furthermore, if $r\in Q$, then no vertex in $Q$ fails as
$Q\subseteq B_{G^{\prime}}(r,1)\subseteq U_{-1,\sigma}\setminus
U^{+}_{0,\sigma}$. Thus we can assume that $r\notin Q$. We proceed by case
analysis; the cases are illustrated in Figure 5.

  * (a)

if $f_{\sigma}$ succeeds on $Q$, then $f_{\sigma}(Q)=\chi_{\sigma}(Q)$. In
particular there is a unique $j$ such that $Q\subseteq U_{j,\sigma}$. As
$f_{j,\sigma}$ is clique-preserving, it contains a clique copy of $Q$. In
particular, $\chi_{\sigma}(Q)$ contain a clique copy of $Q$.

Otherwise, $f_{\sigma}$ fails on $Q$. Then, there is a unique index $j$ such
that the intersection of $Q$ with both $U^{+}_{j,\sigma}$ and
$U^{+}_{j+1,\sigma}$ is non-empty.

  * (b)

First, consider the case that $Q\subseteq U_{j,\sigma}$ (the case $Q\subseteq
U_{j+1,\sigma}$ is symmetric). Here $\chi_{\sigma}(Q)=f_{j,\sigma}(Q)$, and
$\psi_{\sigma}(Q)=\psi_{\sigma}(Q^{F}_{\sigma})=f_{j+1,\sigma}(Q^{F}_{\sigma})$,
where $Q^{F}_{\sigma}=\\{v\in Q\mid\psi_{\sigma}(v)\neq 0\\}$. As
$f_{j,\sigma}$ and $f_{j+1,\sigma}$ are clique-preserving, $\chi_{\sigma}(Q)$
contain a clique copy of $Q$, while $\psi_{\sigma}(Q^{F}_{\sigma})$ contains a
clique copy of $Q^{F}_{\sigma}$.

  * (c)

Finally, consider the case where $Q$ intersect both $U_{j,\sigma}$ and
$U_{j+1,\sigma}$. It holds that
$d_{G^{\prime}}(r,s_{Q})<\frac{8(j+1)}{\delta}+\sigma\leq
d_{G^{\prime}}(r,t_{Q})$, hence $\frac{8(j+1)}{\delta}+\sigma-1\leq
d_{G^{\prime}}(r,s_{Q})$ and
$d_{G^{\prime}}(r,t_{Q})<\frac{8(j+1)}{\delta}+\sigma+1$ (here $s_{Q},t_{Q}\in
Q$ are the closest and farthest vertices from $r$, respectively). Necessarily,
$Q\subseteq U^{+}_{j,\sigma}\cap U^{+}_{j+1,\sigma}$. In particular, as
$f_{j,\sigma}(Q)$, and $f_{j+1,\sigma}(Q)$ are clique-preserving, they contain
clique copies $Q_{1},Q_{2}$ of $Q$ (respectively). Furthermore,
$Q_{1},Q_{2}\subseteq f_{\sigma}(Q)$, and for every vertex $v\in Q$, both
$\chi(v)\cap(Q^{1}\cup Q^{2})$ and $\psi(v)\cap(Q^{1}\cup Q^{2})$ are
singletons.
It remains to prove the additional stretch guarantee. Consider a vertex $v\in
Q$, suppose that $v\in U_{j,\sigma}$ (the case $v\in U_{j+1,\sigma}$ is
symmetric). Here $\chi_{\sigma}(v)=f_{j,\sigma}(v)$ and
$\psi_{\sigma}(v)=f_{j+1,\sigma}(v)$. Consider some vertex $u\in V$, in
similar manner to the general distortion argument, if either
$u\in\Psi\cup\\{r\\}$, or the shortest path from $u$ to $v$ in $G$ goes
through $\Psi\cup\\{r\\}$, then the distance between every two copies in
$f_{\sigma}(v)$ and $f_{\sigma}(u)$ is exactly $d_{G}(u,v)$, and hence
equation (7) holds. Else, $d_{G^{\prime}}(u,v)=d_{G}(u,v)$, and it holds that
$d_{G^{\prime}}(r,u)\geq d_{G^{\prime}}(r,v)-d_{G^{\prime}}(u,v)\geq
d_{G^{\prime}}(r,s_{Q})-1\geq\frac{8(j+1)}{\delta}+\sigma-2$, thus $u\in
U^{+}_{j+1,\sigma}$. Furthermore,
$d_{G_{j+1,\sigma}}(u,v)=d_{G^{\prime}}(u,v)$ (as the entire shortest path
between them is in $U^{+}_{j+1,\sigma}$). By Lemma 1,

$\displaystyle\min\left\\{\max_{u^{\prime}\in\chi(u),v^{\prime}\in\psi(v)}d_{H}(u^{\prime},v^{\prime}),\max_{u^{\prime}\in\psi(u),v^{\prime}\in\psi(v)}d_{H}(u^{\prime},v^{\prime})\right\\}$
$\displaystyle\quad\leq\max_{u^{\prime}\in f_{j+1,\sigma}(u),v^{\prime}\in
f_{j+1,\sigma}(v)}d_{H_{j+1,\sigma}}(u^{\prime},v^{\prime})\,\leq\,d_{G_{j+1,\sigma}}(u,v)+\epsilon
D\,=\,d_{G^{\prime}}(u,v)+\epsilon D\,=\,d_{G}(u,v)+\epsilon
D\leavevmode\nobreak\ .$

∎

Consider a $K_{r}$-minor-free graph $G$, and let $\mathbb{T}$ be its clique-
sum decomposition. That is $G=\cup_{(G_{i},G_{j})\in
E(\mathbb{T})}G_{i}\oplus_{h}G_{j}$ where each $G_{i}$ is a nearly
$h(r)$-embeddable graph. We call the clique involved in the clique-sum of
$G_{i}$ and $G_{j}$ the _joint set_ of the two graphs. Let $\phi_{h}$ be some
function depending only on $h$ such that the treewidth of the graphs
constructed in Lemma 18 is bounded by $\phi_{h}\cdot\frac{\log
n}{\epsilon\cdot\delta}$. The embedding of $G$ is defined recursively, where
some vertices from former levels will be added to future levels as apices. In
order to control the number of such apices, we will use the concept of enhance
minor-free graphs introduced in Definition 9 in Section 6. We will prove the
following lemma by induction on $t$:

######  Lemma 19.

Given an $(r,s,t)$-enhanced minor-free graph $G$ of diameter $D$ with a
specified set $S$ of elevated vertices, and parameters
$\epsilon\in(0,\frac{1}{4})$,$\delta\in(0,1)$, there is a distribution over
one-to-many, clique-preserving, dominating embeddings $f$ into graphs of
treewidth $\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta}+s+h(r)\cdot\log
t$, such that for every vertex $v\in V$, $f(v)$ can be partitioned into sets
$g_{1}(v),g_{2}(v),\dots$ where $\bigcupdot_{j\geq 1}g_{j}(v)=f(v)$.
Furthermore,

  1. 1.

For every $v\in V$, let $q_{v}$ be the maximal index $j$ such that
$g_{j}(v)\neq\emptyset$, then $\mathbb{E}[q_{v}]\leq(1+\delta)^{\log 2t}$. In
addition, if $v\in S$ then $|f(v)|=1$ and thus $q_{v}=1$.

  2. 2.

For every pair of vertices $u,v$, $\min_{j}\max_{u^{\prime}\in
g_{j}(u),v^{\prime}\in g_{1}(v)}d_{H}(u^{\prime},v^{\prime})\leq
d_{G}(u,v)+\epsilon D$.

Assuming Lemma 19, Theorem 5 easily follows.

###### Proof of Theorem 5.

Note that every $K_{r}$-minor-free graph is $(r,0,n)$-enhanced minor-free. We
apply Lemma 19 using parameters $\epsilon$ and
$\delta^{\prime}=\frac{\delta}{2\log 2n}$. For every vertex $v\in V$, let
$g(v)\subseteq f(v)$ be a set containing a single copy from each non empty set
$g_{j}(v)$. Let $\chi(v)=g(v)\cap g_{1}(v)$ be the copy in $g(v)$ from
$g_{1}(v)$. The distortion guarantee is straightforward to verify. The
treewidth of the resulting graph is $\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta^{\prime}}+0+h(r)\cdot\log
n=O_{r}(\frac{\log^{2}n}{\epsilon^{2}})$. Finally, for every vertex $v\in V$,
it holds that $\mathbb{E}[|g(v)|]\leq(1+\frac{\delta}{2\log 2n})^{\log
2n}<e^{\frac{\delta}{2}}<1+\delta$. ∎

The rest of the section is devoted to proving Lemma 19.

###### Proof of Lemma 19.

The claim is proved by induction on $t$. It follows from Lemma 18 that Lemma
19 holds for the base case $t=1$; the treewidth will be
$\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta}+s$ since we add all
elevated vertices to every bag.

We now turn to the induction step. Consider an $(r,s,t)$-enhanced minor-free
graph $G$. Let $G^{\prime}$ be a $K_{r}$-minr-free graph obtained from $G$ by
removing the set $S$ (of size at most $s$). Let $\mathbb{T}$ be the clique-sum
decomposition of $G^{\prime}$ with $t$ pieces. Using Lemma 17, choose a
central piece $\tilde{G}\in\mathbb{T}$ of $\mathbb{T}$. Let
$G_{1},\dots,G_{p}$ be the neighbors of $\tilde{G}$ in $\mathbb{T}$. Note that
$\mathbb{T}\setminus\tilde{G}$ contains $p$ connected components
$\mathbb{T}_{1},\dots,\mathbb{T}_{p}$, where $G_{i}\in\mathbb{T}_{i}$, and
$\mathbb{T}_{i}$ contains at most $|\mathbb{T}|/2=t/2$ pieces. Let $Q_{i}$ be
the clique used in the clique-sum of $G_{i}$ with $\tilde{G}$ in $\mathbb{T}$.
For every $i$, we will add edges between vertices of $Q_{i}$ to all the
vertices in $\mathbb{T}_{i}$; this is equivalent to making $Q_{i}$ into
apices. Every new edge $\\{u,v\\}$ will have weight $d_{G}(u,v)$. Let
$\mathcal{G}_{i}$ be the graph induced on the vertices of $\mathbb{T}_{i}\cup
S$ (and the newly added edges). Note that $\mathcal{G}_{i}$ is an
$(r,s^{\prime},t^{\prime})$-enhanced minor-free graph for
$t^{\prime}\leq\frac{t}{2}$ and $|s^{\prime}|\leq s+|Q_{i}|\leq s+h(r)$.
Further, for every $u,v\in\mathcal{G}_{i}$, it holds that
$d_{\mathcal{G}_{i}}(u,v)=d_{G}(u,v)$, and thus $\mathcal{G}_{i}$ has diameter
at most $D$. Applying the inductive hypothesis to $\mathcal{G}_{i}$, we sample
a dominating embedding $f_{i}$ into $H_{i}$, such that for every
$v\in\mathcal{G}_{i}$ we have $f_{i}(v)=\bigcupdot_{j\geq 1}g_{i,j}(v)$. We
denote by $q_{v}^{i}$ the maximal index such that
$g_{i,q_{v}^{i}}(v)\neq\emptyset$. Note that properties (1) and (2) hold and
furthermore, $H_{i}$ has treewidth $\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s^{\prime}+h(r)\cdot\log
2t^{\prime}\leq\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s+h(r)\cdot\log 2t$. In addition, for a vertex $v\in
S\cup Q_{i}$, $|f_{i}(v)|=1$ (thus $q_{v}^{i}=1$), while for every vertex
$v\in V$, $\mathbb{E}[q_{v}^{i}]\leq(1+\delta)^{\log
2t^{\prime}}\leq(1+\delta)^{\log t}$.

Let $\tilde{\mathcal{G}}$ be the graph induced on $\tilde{G}\cup S$. We apply
Lemma 18 to $\tilde{\mathcal{G}}$ to sample a dominating one-to-many embedding
$\tilde{f}$ into $\tilde{H}$, such that for each vertex
$v\in\tilde{\mathcal{G}}$, $\tilde{f}(v)$ is partitioned into
$\tilde{\chi}(v)$ and $\tilde{\psi}(v)$. $\tilde{H}$ has treewidth
$\phi_{h(r)}\cdot\frac{\log n}{\epsilon\cdot\delta}+s$ (this is by Lemma 18,
we first remove all apices and then add them back). Note also that properties
(1), (2), and (3) hold.

We next describe how to combine the different parts into a single embedding.
The graph (and the induced embedding) will be created by identifying some
vertices in $\tilde{H}$ with vertices in each $H_{i}$. Some of the graphs
$H_{i}$ will be duplicated and we will have two copies of them (depending on
whether $Q_{i}$ failed in $\tilde{f}$). Note that the set $S$ has a single
copy everywhere, and thus for every $v\in S$, we will simply identify all the
vertices $\tilde{f}(v),f_{1}(v),\dots,f_{p}(v)$.

$\mbox{For a vertex}\leavevmode\nobreak\ v\in\tilde{\mathcal{G}}\mbox{, set
}\quad g_{1}(v)=\tilde{\chi}(v)\quad\mbox{ and }\quad
g_{2}(v)=\tilde{\psi}(v)\leavevmode\nobreak\ .$

Consider some $i\in[p]$. Note that the clique $Q_{i}$ belongs to $S_{i}$. In
particular, for every vertex $v\in Q_{i}$, $f_{i}(v)$ is a singleton, and
$f_{i}(Q_{i})$ is a clique. We continue w.r.t. the $3$ cases in Lemma 18 (see
Figure 5 for an illustration of the cases):

  * •

$\tilde{f}$ succeeds on $Q_{i}$: Here $\tilde{\psi}(Q_{i})=\emptyset$, and
$\tilde{\chi}(Q_{i})=g_{q}(Q_{i})$ contains a clique copy
$Q^{1}_{i}\subseteq\tilde{\chi}(Q_{i})$ of $Q_{i}$. We simply identify each
vertex in $f_{i}(Q_{i})$ with the corresponding copy in $Q^{1}_{i}$. We will
abuse notation and refer to $H_{i}$ as $H_{i}^{1}$, to $f_{i}$ as $f_{i}^{1}$,
and to $g_{i,j}$ as $g^{1}_{i,j}$.

$\mbox{For a vertex}\leavevmode\nobreak\
v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}},\quad\mbox{ for every }j\geq
1\quad\mbox{ set }\quad g_{j}(v)=g^{1}_{i,j}(v)\leavevmode\nobreak\ .$

  * •

$\tilde{f}$ fails on $Q_{i}$, and $\tilde{\chi}(Q_{i})$ contains a clique copy
of $Q_{i}$: Denote by $Q_{i}^{1}\subseteq\tilde{\chi}(Q_{i})$ the promised
clique copy of $Q_{i}$. In addition, $\tilde{\psi}(Q^{F}_{i})$ is guaranteed
to contain a clique copy $Q_{i}^{2}$ of $Q^{F}_{i}=\\{v\in
Q_{i}\mid\tilde{\psi}(v)\neq\emptyset\\}$. We duplicate $H_{i}$ into two
graphs $H_{i}^{1}$ and $H_{i}^{2}$ with respective duplicate embeddings
$f_{i}^{1},f_{i}^{2}$. However, the vertices of $Q_{i}\setminus Q_{i}^{F}$ are
removed from $H_{i}^{2}$ and $f_{i}^{2}$. We combine $\tilde{H}$ with
$H_{i}^{1}$ (resp. $H_{i}^{2}$) by combining a clique copy from
$\tilde{\chi}(Q_{i})$ (resp. $\tilde{\psi}(Q^{F}_{i})$) with the corresponding
vertices from $f_{i}^{1}(Q_{i})$ (resp. $f_{i}^{2}(Q^{F}_{i})$) (recall that
they are apices and thus have a single copy).

    * –

For every vertex $v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$ where
$q_{v}^{i}$ is the maximal index $j$ such that $g_{i,j}(v)\neq\emptyset$. For
every $j\in[1,q_{v}^{i}]$, set $g_{j}(v)=g^{1}_{i,j}(v)$ to be the
corresponding copies from $f^{1}_{i}(v)$, and
$g_{q_{v}^{i}+j}(v)=g^{2}_{i,j}(v)$ be the corresponding copies from
$f^{2}_{i}(v)$.

  * •

$\tilde{f}$ fails on $Q_{i}$, and $\tilde{f}(Q_{i})$ contains two clique
copies $Q_{i}^{1},Q_{i}^{2}$ of $Q_{i}$ such that for every $v\in Q_{i}$,
$Q_{i}^{1}\cup Q_{i}^{2}$ intersects both $\tilde{\chi}(v)$ and
$\tilde{\psi}(v)$: We duplicate $H_{i}$ into two graphs $H_{i}^{1}$ and
$H_{i}^{2}$ with respective duplicate embeddings $f_{i}^{1},f_{i}^{2}$. We
combine $\tilde{H}$ with $H_{i}^{1}$ (resp. $H_{i}^{2}$) by identifying
$Q_{i}^{1}$ (resp. $Q_{i}^{2}$) with $f_{i}^{1}(Q_{i})$ (resp.
$f_{i}^{2}(Q_{i})$) (recall that they are apices and thus have a single copy).

    * –

For every vertex $v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$ where
$q_{v}^{i}$ is the maximal index $j$ such that $g_{i,j}(v)\neq\emptyset$. For
every $j\in[1,q_{v}^{i}]$, set $g_{j}(v)=g^{1}_{i,j}(v)$ be the corresponding
copies from $f^{1}_{i,j}(v)$, and $g_{q_{v}^{i}+j}(v)=g^{2}_{i,j}(v)$ be the
corresponding copies from $f^{2}_{i,j}(v)$.

We claim next that $f,g_{1},g_{2},\dots$ fulfill all the required properties.
First, note that $f$ is clique-preserving as every clique must be contained in
either $\tilde{\mathcal{G}}$ or some $\mathcal{G}_{i}$. Second, clearly $f$ is
dominating as the weight of every edge between a vertex in $f(v)$ and $f(u)$
is $d_{G}(u,v)$. Third, as we only identify between cliques, the graph $H$ has
treewidth

$\max\left\\{\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s+h(r)\cdot\log
2t\quad,\quad\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s\right\\}\quad=\quad\phi_{h(r)}\cdot\frac{\log
n}{\epsilon\cdot\delta}+s+h(r)\cdot\log 2t$

Forth, it holds by definition that for every vertex $v\in V$,
$f(v)=\bigcupdot_{j}g_{j}(v)$.

Next, we prove property (1). Clearly, for a vertex $v\in S$, we identify
between all its copies and thus $f(v)$ is a singleton. Consider a vertex $v\in
V$, if $v\in\tilde{\mathcal{G}}$, then by Lemma 18

$\mathbb{E}[q_{v}]=1+\Pr\left[\tilde{f}\text{ fails on }v\right]\leq
1+\delta\leavevmode\nobreak\ .$

Else, consider $v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$ for some $i$,
and denote by $q_{v}^{i}$ the maximal index $j$ such that $g_{i,j}$ is non-
empty. We have

$\displaystyle\mathbb{E}[q_{v}]$
$\displaystyle=\mathbb{E}[q_{v}^{i}]\cdot\Pr\left[\tilde{f}\text{ succeeds on
}Q_{i}\right]+\mathbb{E}[2q_{v}^{i}]\cdot\Pr\left[\tilde{f}\text{ fails on
}Q_{i}\right]$
$\displaystyle=\mathbb{E}[q_{v}^{i}]\cdot\left(1+\Pr\left[\tilde{f}\text{
fails on }Q_{i}\right]\right)$ $\displaystyle\leq(1+\delta)^{\log
2\cdot\frac{t}{2}}\cdot(1+\delta)=(1+\delta)^{\log 2t}\leavevmode\nobreak\ ,$

where the first equality is because we have two copies of $H_{i}$ iff
$\tilde{f}$ fails on $Q_{i}$. The second equality is because $\Pr\left[f\text{
succeeds on }Q_{i}\right]=1-\Pr\left[f\text{ fails on }Q_{i}\right]$. The
final inequality follows by the induction hypothesis and Lemma 18.

Finally, we prove property (2). Consider a pair of vertices $u,v\in V$. We
proceed by case analysis.

  * •

If a shortest path from $u$ to $v$ goes through a vertex $z\in S$ (this
includes the case where either $u$ or $v$ are in $S$): Then

$\displaystyle\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})\quad\leq\quad\max_{u^{\prime}\in
f(u),v^{\prime}\in f(v)}d_{H}(u^{\prime},v^{\prime})$
$\displaystyle\qquad\quad\leq\quad\max_{u^{\prime}\in f(u),v^{\prime}\in
f(v)}d_{H}(u^{\prime},f(z))+d_{H}(f(z),v^{\prime})\quad=\quad
d_{G}(u,z)+d_{G}(z,v)\quad=\quad d_{G}(u,v)\leavevmode\nobreak\ .$

For the remaining cases, we assume that $d_{G^{\prime}}(u,v)=d_{G}(u,v)$
(recall that $G^{\prime}=G[V\setminus S]$).

  * •

Else, if both $u,v\in\tilde{\mathcal{G}}$: Then by Lemma 18,

$\displaystyle\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})$
$\displaystyle\leq\min\left\\{\max_{u^{\prime}\in\chi(u),v^{\prime}\in\chi(v)}d_{H}(u^{\prime},v^{\prime}),\max_{u^{\prime}\in\psi(u),v^{\prime}\in\chi(v)}d_{H}(u^{\prime},v^{\prime})\right\\}$
$\displaystyle\leq d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$

  * •

Else, if $u\in\tilde{\mathcal{G}}$ and there is an $i\in[p]$ such that
$v\in\mathcal{G}_{i}\setminus\tilde{\mathcal{G}}$: There is necessarily a
vertex $x\in Q_{i}$ such that there is a shortest path from $u$ to $v$ in $G$
going through $x$. Note by the construction that (a) the copy $g_{1}(v)$
belongs to $H^{1}_{i}$ (a copy of $H_{i}$), (b) there is an edge from
$g_{1}(v)$ to a copy of $x$ in $f_{i}^{1}(Q_{i})$ and (c) a clique copy
$Q_{i}^{1}\subseteq\tilde{f}(Q)$ of $Q$ is identified with $f_{i}^{1}(Q_{i})$
(a set of singletons). We continue by case analysis:

    * –

If either $\tilde{f}$ succeeds on $Q_{i}$, or
$Q_{i}^{1}\subseteq\tilde{\chi}(Q_{i})$. Then there is a copy $\hat{x}$ of $x$
in $g_{1}(x)\cap Q_{i}^{1}$. It holds that

$\displaystyle\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})$
$\displaystyle\leq\min_{j}\left(\max_{u^{\prime}\in
g_{j}(u)}d_{H}(u^{\prime},\hat{x})+\max_{v^{\prime}\in
g_{1}(v)}d_{H}(\hat{x},v^{\prime})\right)$ $\displaystyle\leq
d_{G}(u,x)+\epsilon D+d_{G}(x,v)=d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$
(8)

where the second inequality follows by the second case (as
$x\in\tilde{\mathcal{G}}$), and the fact that there is an edge in $H$ between
$\hat{x}$ to every vertex in $g_{1}(v)$.

    * –

Else, $\tilde{f}(Q_{i})$ contains two clique copies $Q_{i}^{1},Q_{i}^{2}$ of
$Q_{i}$. Note that $\hat{x}$ can belong to either $g_{1}(x)=\tilde{\chi}(x)$
or $g_{2}(x)=\tilde{\psi}(x)$. Nevertheless, by using either equation (6) or
(7) we have that $\min_{j}\max_{u^{\prime}\in
g_{j}(u)}d_{H}(u^{\prime},\hat{x})\leq d_{G}(u,x)+\epsilon D$. As there is
edge in $H$ between $\hat{x}$ to every vertex in $g_{1}(v)$, we conclude that
equation (8) holds.

  * •

Else, if $v\in\tilde{\mathcal{G}}$ and there is an $i\in[p]$ such that
$u\in\mathcal{G}_{i}\setminus{\mathcal{G}}$: There is necessarily a vertex
$x\in Q_{i}$ such that there is a shortest path from $u$ to $v$ in $G$ going
through $x$. By the second case, there is an index $j^{\prime}$ such that
$\max_{x^{\prime}\in g_{j^{\prime}}(x),v^{\prime}\in
g_{1}(v)}d_{H}(x^{\prime},u^{\prime})\leq d_{G}(x,v)+\epsilon D$. As
$x\in\tilde{\mathcal{G}}$, $j^{\prime}\in\\{1,2\\}$. In any case, a copy of
$H_{i}$ was assigned to $\tilde{H}$ by identifying clique vertices. In
particular, some vertex $\hat{x}\in g_{j^{\prime}}(x)$ was identified with the
apex vertex $f_{i}(x)$ (from the relevant copy). Therefore there is an index
$j^{\prime\prime}$ such that $\hat{x}$ has edges towards all the vertices in
$g_{j^{\prime\prime}}(u)$. We conclude,

$\displaystyle\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})$ $\displaystyle\leq\max_{u^{\prime}\in
g_{j^{\prime\prime}}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},\hat{x})+d_{H}(\hat{x},v^{\prime})$
$\displaystyle\leq d_{G}(u,x)+\max_{x^{\prime}\in
g_{j^{\prime}}(x),v^{\prime}\in g_{1}(v)}d_{H}(x^{\prime},v^{\prime})$
$\displaystyle\leq d_{G}(u,x)+d_{G}(x,v)+\epsilon D=d_{G}(u,v)+\epsilon
D\leavevmode\nobreak\ .$

  * •

Else, if there is an $i\in[p]$ such that
$u,v\in\mathcal{G}_{i}\setminus{\mathcal{G}}$: There is a copy of $H_{i}$
which embedded as is into $H$ and contains all the vertices in $g_{1}(v)$. By
the induction hypothesis

$\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})\leq\min_{j}\max_{u^{\prime}\in
g_{i,j}(u),v^{\prime}\in g_{i,1}(v)}d_{H_{i}}(u^{\prime},v^{\prime})\leq
d_{\mathcal{G}_{i}}(u,v)+\epsilon D=d_{G}(u,v)+\epsilon D\leavevmode\nobreak\
.$

  * •

Else, there are $i\neq i^{\prime}\in[p]$ such that
$u\in\mathcal{G}_{i}\setminus{\mathcal{G}}$ and
$v\in\mathcal{G}_{i^{\prime}}\setminus{\mathcal{G}}$: There are necessarily
vertices $y\in Q_{i}$ and $x\in Q_{i^{\prime}}$ such that there is a shortest
path from $u$ to $v$ in $G$ going through $y$ and $x$. Note that the copy
$H^{1}_{i^{\prime}}$ of $H_{i^{\prime}}$ containing $g_{1}(v)$ was added to
$H$ by identifying $f^{1}_{i^{\prime}}(Q_{i^{\prime}})$ with a clique copy
$Q_{i^{\prime}}^{1}$ of $Q_{i^{\prime}}$. In particular, there is a copy
$\hat{x}\in Q_{i^{\prime}}^{1}$ of $x$ which has edges towards all the
vertices in $g_{1}(v)$. There are two cases:

    * –

If $\hat{x}\in g_{1}(x)$, then by the third case there is an index $j$ such
that $\max_{u^{\prime}\in
g_{j}(u)}d_{H}(u^{\prime},\hat{x})\leq\max_{u^{\prime}\in
g_{j}(u),x^{\prime}\in g_{1}(x)}d_{H}(u^{\prime},x^{\prime})\leq
d_{G}(u,x)+\epsilon D$. As there is an edge from $\hat{x}$ to every copy of
$v$ in $g_{1}(v)$, we conclude that $\max_{u^{\prime}\in
g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})\leq\max_{u^{\prime}\in
g_{j}(u)}d_{H}(u^{\prime},\hat{x})+\max_{v^{\prime}\in
g_{1}(x)}d_{H}(\hat{x},v^{\prime})\leq d_{G}(u,x)+\epsilon
D+d_{G}(x,v)=d_{G}(u,v)+\epsilon D$.

    * –

Else, $\hat{x}\in g_{2}(x)$. Necessarily $\tilde{f}$ failed on
$Q_{i^{\prime}}$ and $\tilde{f}(Q_{i^{\prime}})$ contains two clique copies
$Q_{i^{\prime}}^{1},Q_{i^{\prime}}^{2}$ of $Q_{i^{\prime}}$. It holds that
$g_{2}(x)=\tilde{\psi}(x)$, thus by Lemma 18 (case 3.(c)) there is an index
$j\in\\{1,2\\}$ such that $\max_{y^{\prime}\in
g_{j}(y)}d_{H}(y^{\prime},\hat{x})\leq\max_{y^{\prime}\in
g_{j}(y),x^{\prime}\in\tilde{\psi}(x)}d_{H}(y^{\prime},x^{\prime})\leq
d_{G}(x,y)+\epsilon D$. Let $\hat{y}\in Q_{i}^{j}\subseteq g_{j}(Q_{i})$ be
the copy of $y$ from the corresponding clique copy. Note that there is an edge
from $\hat{x}$ to every copy of $v$ in $g_{1}(v)$. Farther, there is an index
$j^{\prime\prime}$ such that $\hat{y}$ has edges towards all the vertices in
$g_{j^{\prime\prime}}(u)$. We conclude,

$\displaystyle\min_{j}\max_{u^{\prime}\in g_{j}(u),v^{\prime}\in
g_{1}(v)}d_{H}(u^{\prime},v^{\prime})$ $\displaystyle\leq\max_{u^{\prime}\in
g_{j^{\prime\prime}}(u)}d_{H}(u^{\prime},\hat{y})+d_{H}(\hat{y},\hat{x})+\max_{v^{\prime}\in
g_{1}(v)}d_{H}(\hat{x},v^{\prime})$ $\displaystyle\leq
d_{G}(u,y)+\max_{y^{\prime}\in g_{j}(y),x^{\prime}\in
g_{2}(x)}d_{H}(y^{\prime},x^{\prime})+d_{G}(x,v)$ $\displaystyle\leq
d_{G}(u,y)+d_{G}(y,x)+\epsilon D+d_{G}(x,v)=d_{G}(u,v)+\epsilon
D\leavevmode\nobreak\ .$

∎

######  Remark 4.

The clan embedding in Theorem 5 directly implies a weaker version of Theorem
4, where the only difference is that the distortion is only for pairs where
both $u,v\in M$ and not only $u\in M$. Note that this weaker version is still
strong enough for our application to the $\rho$-independent set problem in
Theorem 7.
Sketch: sample a clan embedding $(f,\chi)$ using Theorem 5. Return $g=\chi$
with the set $M=\\{v\in V\leavevmode\nobreak\ \mid\leavevmode\nobreak\
|f(v)|=1\\}$. The weaker distortion guarantee and failure probability are
straightforward.

##  8 Applications

Organization: in Sections 8.1, 8.2 and 8.3 we provide the algorithms (and
proofs) to our QPTAS ${}^{\ref{foot:approximationSchemes}}$ for metric
$\rho$-independent set problem, QPTAS for metric $\rho$-dominating set
problem, and compact routing scheme, respectively.

We begin with a discussion on approximation schemes for metric
$\rho$-dominating/independent set problems in bounded treewidth graphs. In the
$(k,r)$-center problem we are given a graph $G=(V,E,w)$, and the goal is to
find a set $S$ of centers of cardinality at most $r$ such that every vertex
$v\in V$ is at distance at most $r$ from some center $u\in S$. Katsikarelis,
Lampis and Paschos [KLP19] provided a PTAS
${}^{\ref{foot:approximationSchemes}}$ for the $(k,r)$-center problem in
treewidth $\mathrm{tw}$ graphs using a dynamic programming approach.
Specifically, for any parameters $k,r\in\mathbb{N}$ and $\epsilon\in(0,1)$,
they provided an algorithm running in
$O(\frac{\mathrm{tw}}{\epsilon})^{\mathrm{tw}}\cdot\mathrm{poly}(n)$ time that
either returns a solution to the $(k,(1+\epsilon)r)$-center problem, or
(correctly) declares that there is no valid solution to the $(k,r)$-center
problem in $G$. This dynamic programming can be easily generalized to the case
where there is a measure $\mu:V\rightarrow\mathbb{R}^{+}$, and terminal set
${\cal K}\subset V$. Specifically, the algorithm will either return a set $S$
of measure $\mu(S)\leq k$, such that every vertex $v\in{\cal K}$ is at
distance at most $(1+\epsilon)r$ from $S$, or will declare there is no set $S$
of measure at most $k$ at distance at most $r$ from every vertex in ${\cal
K}$.

As was observed by Fox-Epstein et al. [FKS19], using [KLP19] one can construct
a bicriteria PTAS for the metric $\rho$-dominating set problem in treewidth
$\mathrm{tw}$ graphs with
$O(\frac{\mathrm{tw}}{\epsilon})^{\mathrm{tw}}\cdot\mathrm{poly}(n)$ running
time. [FKS19] studied the basic version (with uniform measure and ${\cal
K}=V$), however this observation holds for the general case as well. In a
follow-up paper, Katsikarelis et al. [KLP20] constructed a similar dynamic
programming for the $\rho$-independent problem with the same
$O(\frac{\mathrm{tw}}{\epsilon})^{\mathrm{tw}}\cdot\mathrm{poly}(n)$ running
time. It could also be generalized to work with a measure $\mu$. This dynamic
programming was also promised to appear in the full version of [FKS19]. We
conclude this discussion:

######  Theorem 12 ([KLP19, KLP20]).

There is a bicriteria polynomial approximation scheme (PTAS) for both metric
$\rho$-independent set and $\rho$-dominating set problems in treewidth
$\mathrm{tw}$ graphs with running time
$O(\frac{\mathrm{tw}}{\epsilon})^{\mathrm{tw}}\cdot\mathrm{poly}(n)$.

###  8.1 QPTAS for the $\rho$-Independent Set Problem in Minor-Free Graphs

This subsection is devoted to proving the following theorem: See 7

###### Proof.

Create a new graph $G^{\prime}$ from $G$ by adding a single vertex $\psi$ at
distance $\frac{3}{4}\rho$ from all the other vertices. $G^{\prime}$ is
$K_{r+1}$-minor free. Note that for every $u,v\in Y$, it holds that
$d_{G^{\prime}}(u,v)=\min\\{\frac{3}{2}\rho,d_{G}(u,v)\\}$. Thus $G^{\prime}$
has diameter at most $\frac{3}{2}\rho$. Furthermore, for every
$\rho^{\prime}\in(0,\frac{3}{2}\rho)$, a set $S\subseteq V$ is a
$\rho^{\prime}$-independent set in $G$ if and only if $S$ is a
$\rho^{\prime}$-independent set in $G^{\prime}$. Using Theorem 4 with
parameters $\epsilon^{\prime}=\frac{\epsilon}{2}$ and
$\delta=\frac{\epsilon}{4}$, let $g$ be an embedding of $G^{\prime}$ into a
treewidth-$O_{r}(\frac{\log^{2}n}{\epsilon^{2}})$ graph $H$ with a set
$M\subseteq V\cup\\{\psi\\}$ such that (1) for every $u,v\in M$,
$d_{H}(g(u),g(v))\leq
d_{G^{\prime}}(u,v)+\frac{\epsilon}{2}\cdot\frac{3}{2}\rho<d_{G^{\prime}}(u,v)+\epsilon\rho$,
and (2) for every $v\in V$, $\Pr[v\in M]\geq 1-\frac{\epsilon}{4}$.

Define a new measure $\mu_{H}$ in $H$, where for each $v\in G^{\prime}$,

$\mu_{H}(v^{\prime})=\begin{cases}0&v^{\prime}\notin g(V\cap M)\\\
\mu(v)&\text{else, }g(v)=v^{\prime}\text{ for some }v\in
M\setminus\\{\psi\\}\end{cases}\qquad.$

In particular, $\mu_{H}(g(\psi))=0$. Using Theorem 12, we find a
$(1-\frac{\epsilon}{2})\rho$-independent set $S_{H}$ w.r.t. $\mu_{H}$, such
that for every $\rho$-independent set $\tilde{S}$ in $H$ it holds that
$\mu_{H}(S_{H})\geq(1-\frac{\epsilon}{2})\mu_{H}(\tilde{S})$. We can assume
that $S_{H}\subseteq g(M)$, as the measure of all vertices out of $g(M)$ is
$0$. We will return $S=g^{-1}(S_{H})$; note that $S\subseteq M$. First, we
argue that $S$ is a $(1-\epsilon)\rho$-independent set. For every $u,v\in S$,
$g(u),g(u)\in S_{H}$ thus

$(1-\frac{\epsilon}{2})\rho\leq d_{H}(g(u),g(v))\leq
d_{G^{\prime}}(u,v)+\frac{\epsilon}{2}\rho\leq
d_{G}(u,v)+\frac{\epsilon}{2}\rho\leavevmode\nobreak\ ,$

implying $d_{G}(u,v)\geq(1-\epsilon)\rho$.

Let $S_{\mathrm{opt}}$ be a $\rho$-independent set w.r.t. $d_{G}$ of maximal
measure. As $g$ is dominating embedding, $g(S_{\mathrm{opt}}\cap M)$ is a
$\rho$-independent set in $H$. By linearity of expectation
${\mathbb{E}[\mu(S_{\mathrm{opt}}\setminus M)]=\sum_{v\in
S_{\mathrm{opt}}}\mu(v)\cdot\Pr\left[v\notin
M\right]\leq\frac{\epsilon}{4}\cdot\mu(S_{\mathrm{opt}})}$. Using Markov
inequality

$\Pr\left[\mu(S_{\mathrm{opt}}\cap
M)<(1-\frac{\epsilon}{2})\mu(S_{\mathrm{opt}})\right]=\Pr\left[\mu(S_{\mathrm{opt}}\setminus
M)\geq\frac{\epsilon}{2}\mu(S_{\mathrm{opt}})\right]\leq\frac{\mathbb{E}[\mu(S_{\mathrm{opt}}\setminus
M)]}{\frac{\epsilon}{2}\mu(S_{\mathrm{opt}})}\leq\frac{1}{2}\leavevmode\nobreak\
.$

Thus, with probability at least $\frac{1}{2}$, $H$ contains a
$\rho$-independent set $g(S_{\mathrm{opt}}\cap M)$ of measure
${\mu_{H}(g(S_{\mathrm{opt}}\cap M))=\mu(S_{\mathrm{opt}}\cap
M)\geq(1-\frac{\epsilon}{2})\mu(S_{\mathrm{opt}})}$. If this event indeed
occurs, the independent set $S_{H}$ returned by [FKS19] algorithm will be of
measure greater than
$(1-\frac{\epsilon}{2})(1-\frac{\epsilon}{2})\mu(S_{\mathrm{opt}})>(1-\epsilon)\mu(S_{\mathrm{opt}})$.
High probability could be obtained by repeating the above algorithm $O(\log
n)$ times and returning the independent set of maximal cardinality among the
observed solutions. ∎

######  Remark 5.

The algorithm above can be derandomized as follows: first note that the
algorithm from Theorem 12 is deterministic. Next, during the construction in
the proof of Theorem 4, each time we execute Lemma 15 we pick $\sigma\in
O(\frac{1}{\delta})$ uniformly at random, where
$\delta=\Theta(\frac{\epsilon}{\log n})$. As we bound the probability of
$\Pr[v\notin M]$ using a simple union bound, it will still hold if we pick the
same $\sigma$ in all the executions of Lemma 15. We conclude that we can
sample the embedding of Theorem 4 from a distribution with support size
$O(\frac{\log n}{\epsilon})$. A derandomization follows.

###  8.2 QPTAS for the $\rho$-Dominating Set Problem in Minor-Free Graphs

We restate the main theorem in this section for convenience. See 8

###### Proof.

Similarly to Theorem 7, we start by constructing an auxiliary graph
$G^{\prime}$ from $G$ by adding a single vertex $\psi$ at distance $2\rho$
from all the other vertices. Extend the measure $\mu$ to $\psi$ by setting
$\mu(\psi)=\infty$. For every $u,v\in V$ it holds that
$d_{G^{\prime}}(u,v)=\min\\{4\rho,d_{G}(u,v)\\}$. It follows that $G^{\prime}$
is a $K_{r+1}$-minor-free graph with diameter bounded by $4\rho$. In
particular, for every $\rho^{\prime}\in(0,2\rho)$, a set $S\subseteq V$ is
$\rho^{\prime}$-dominating set (w.r.t. ${\cal K}$) in $G$ if and only if $S$
is $\rho^{\prime}$ dominating set in $G^{\prime}$ (w.r.t. ${\cal K}$). Using
Theorem 5 with parameters $\epsilon^{\prime}=\frac{\epsilon}{12}$ and
$\delta=\frac{\epsilon}{6}$, let $(f,\chi)$ be a clan embeddings of
$G^{\prime}$ into a treewidth $O_{r}(\frac{\log^{2}n}{\epsilon^{2}})$ graph
$H^{\prime}$ with additive distortion $\epsilon^{\prime}\cdot
4\rho=\frac{\epsilon}{3}\rho$. Define a new measure $\mu_{H}$ in $H$, where
for each $v^{\prime}\in H$,

$\mu_{H}(v^{\prime})=\begin{cases}\infty&v^{\prime}\notin f(V)\\\
\mu(v)&v^{\prime}\in f(v)\end{cases}$

Set also ${\cal K}_{H}=\chi({\cal K})\subseteq H$ to be our set of terminals.
Using Theorem 12, we find a $(1+\frac{\epsilon}{3})^{2}\rho$-dominating set
$A_{H}$, such that for every $\chi(v)\in{\cal K}_{H}$,
$d_{H}(\chi(v),A_{H})\leq(1+\frac{\epsilon}{3})^{2}\rho$, and for every
$(1+\frac{\epsilon}{3})\rho$-dominating set $\tilde{A}$ w.r.t. ${\cal K}_{H}$
it holds that $\mu_{H}(A_{H})\leq(1+\frac{\epsilon}{3})\mu_{H}(\tilde{A})$. We
can assume that $A_{H}$ contains only vertices from $f(V)$ (as all other
vertices have measure $\infty$, while ${\cal K}_{H}$ itself is legal solution
of finite measure). We will return $A=f^{-1}(A_{H})=\\{u\in V\mid f(u)\cap
A_{H}\neq\emptyset\\}$.

First, we argue that $A$ is a $(1+\epsilon)\rho$-dominating set. For every
vertex $v\in{\cal K}$, $\chi(v)\in{\cal K}_{H}$. Therefore there is a vertex
$\hat{u}\in A_{H}$ such that
$d_{H}(\chi(v),\hat{u})\leq(1+\frac{\epsilon}{3})^{2}\rho$. In particular, our
solution $A$ contains the vertex $u$ such that $\hat{u}\in f(u)$. As
$(f,\chi)$ is dominating embedding we conclude

$d_{G}(u,v)\leq\min_{u^{\prime}\in f(u)}d_{H}(u^{\prime},\chi(v))\leq
d_{H}(\hat{u},\chi(v))\leq(1+\frac{\epsilon}{3})^{2}\rho<(1+\epsilon)\rho\leavevmode\nobreak\
.$

Second, we argue that $A$ has nearly optimal measure. Let $A_{\mathrm{opt}}$
be a $\rho$-dominating set in $G$ w.r.t. ${\cal K}$ of minimal measure. As
$(f,\chi)$ has additive distortion $\frac{\epsilon}{3}\rho$,
$f(A_{\mathrm{opt}})$ is a $(1+\frac{\epsilon}{3})\rho$-dominating set in $H$
(w.r.t. ${\cal K}_{H}$). Indeed, consider a vertex $\chi(v)\in{\cal K}_{H}$
(for $v\in{\cal K}$). There is a vertex $u\in A_{\mathrm{opt}}$ such that
$d_{G}(u,v)\leq\rho$. It holds that

$d_{H}(f(A_{\mathrm{opt}}),\chi(v))\leq\min_{u^{\prime}\in
f(u)}d_{H}(u^{\prime},\chi(v))\leq
d_{G}(u,v)+\frac{\epsilon}{3}\rho\leq(1+\frac{\epsilon}{3})\rho$

By Theorem 12, we will find a $(1+\frac{\epsilon}{3})^{2}\rho$-dominating set
of measure at most $(1+\frac{\epsilon}{3})\mu_{H}(f(A_{\mathrm{opt}}))$ in
$H$. By linearity of expectation,

$\mathbb{E}\left[\mu_{H}(f(A_{\mathrm{opt}})\right]=\sum_{u\in
A_{\mathrm{opt}}}\mu(u)\cdot\mathbb{E}\left[\left|f(u)\right|\right]\leq(1+\frac{\epsilon}{6})\cdot\mu(A_{\mathrm{opt}})\leavevmode\nobreak\
.$

From the other hand,
$\mu_{H}(f(A_{\mathrm{opt}}))\geq\mu_{H}(\chi(A_{\mathrm{opt}}))=\mu(A_{\mathrm{opt}})$.
Using Markov inequality,

$\displaystyle\Pr\left[\mu_{H}(f(A_{\mathrm{opt}}))\geq(1+\frac{\epsilon}{3})\cdot\mu(A_{\mathrm{opt}})\right]$
$\displaystyle=\Pr\left[\mu_{H}(f(A_{\mathrm{opt}}))-\mu(A_{\mathrm{opt}})\geq\frac{\epsilon}{3}\mu(A_{\mathrm{opt}})\right]$
$\displaystyle\leq\frac{\mathbb{E}[\mu_{H}(f(A_{\mathrm{opt}}))-\mu(A_{\mathrm{opt}})]}{\frac{\epsilon}{3}\mu(A_{\mathrm{opt}})}\leq\frac{\frac{\epsilon}{6}}{\frac{\epsilon}{3}}=\frac{1}{2}\leavevmode\nobreak\
.$

Thus with probability at least $\frac{1}{2}$, $H$ contains
$(1+\frac{\epsilon}{3})\rho$-dominating set of measure
$(1+\frac{\epsilon}{3})\mu(A_{\mathrm{opt}})$. If this event indeed occurs,
the dominating set $A_{H}$ returned by Theorem 12 will be of measure at most
$(1+\frac{\epsilon}{3})^{2}\mu(A_{\mathrm{opt}})<(1+\epsilon)\mu(A_{\mathrm{opt}})$.
High probability could be obtained by repeating the algorithm above $O(\log
n)$ times and returning the set of minimum measure among the observed
dominating sets. ∎

###  8.3 Compact Routing Scheme

We restate the main theorem of this subsection for convenience. We begin by
presenting a result of Thorup and Zwick [TZ01] regarding routing in a tree.

######  Theorem 13 ([TZ01]).

For any tree $T=(V,E)$ (where $|V|=n$), there is a routing scheme with stretch
$1$ that has routing tables of size $O(1)$ and labels (and headers) of size
$O(\log n)$.

Recall that we measure space in machine words, where each word is $\Theta(\log
n)$ bits. We stress out the extremely short routing table size obtained in
[TZ01]. Note that when a vertex receives a packet with a header, it makes the
routing decision based only on the routing table, and do not require any
knowledge of the label of itself. In particular, the routing table contains a
unique identifier of the vertex.

Additional ingredient that our construction will require is that of a
_distance labeling scheme_ for trees. A _distance labeling_ , assigns to each
point $x\in X$ a label $l(x)$, and there is an algorithm $\mathcal{A}$
(oblivious to $(X,d)$) that provided labels $l(x),l(y)$ of arbitrary $x,y\in
X$, can compute $d_{G}(u,v)$. Specifically, a distance labeling is said to
have _stretch_ $t\geq 1$ if

$\forall x,y\in X,\qquad d(x,y)\leq\mathcal{A}\left(l(x),l(y)\right)\leq
t\cdot d(x,y).$

We refer to [FGK20] for an overview of distance labeling schemes in different
regimes (and comparison with metric embedding, see also [Pel00, GPPR04, TZ05,
EFN18]). Exact distance labeling on an $n$-vertex tree requires $\Theta(\log
n)$ words [AGHP16], which is already larger than the routing table size we are
aiming for. Nonetheless, Freedman et al. [FGNW17] (improving upon [AGHP16,
GKK+01]) showed that for any $n$-vertex unweighted tree, and
$\epsilon\in(0,1)$, one can construct an $(1+\epsilon)$-labeling scheme with
labels of size $O(\log\frac{1}{\epsilon})$ words.

######  Theorem 14 ([FGNW17]).

For any $n$-vertex tree $T=(V,E)$ with polynomial aspect ratio
${}^{\ref{foot:aspectRatio}}$, and parameter $\epsilon\in(0,1)$, there is a
distance labeling scheme with stretch $1+\epsilon$, and
$O(\log\frac{1}{\epsilon})$ label size.

We will use Theorem 14 for fixed $\epsilon$. For this case the theorem can be
extended to weighted trees with polynomial aspect ratio (by subdividing
edges).

###### Proof of Theorem 6.

We combine Theorem 3 with Theorem 13 and Theorem 14 to construct a compact
routing scheme. We begin by sampling a spanning clan embedding $(f,\chi)$ of
$G$ into a tree $T$ with distortion $O(k\log\log n)$ such that for every
vertex $v\in V$, $\mathbb{E}[|f(v)|]\leq n^{1/k}$. Using Theorem 14, we
construct a distance labeling scheme for $T$ with stretch at most $2$ and
$O(1)$ label size. That is, each vertex $v^{\prime}\in T$ has a label $l_{\rm
dl}(v^{\prime})$ of constant size, such that for every pair
$v^{\prime},u^{\prime}\in T$,
$d_{T}(v^{\prime},u^{\prime})\leq\mathcal{A}\left(l_{\rm
dl}(v^{\prime}),l_{\rm dl}(u^{\prime})\right)\leq 2\cdot
d_{T}(v^{\prime},u^{\prime})$ (${\rm dl}$ stands for distance labeling).

Using Theorem 13, we construct a compact routing scheme for $T$, such that
each $v^{\prime}\in T$ has a label $\ell_{\rm crs}(v^{\prime})$ of size
$O(\log|T|)=O(\log n)$, and routing table $\tau_{\rm crs}(v^{\prime})$ of size
$O(1)$ (${\rm crs}$ stands for compact routing scheme). We construct a compact
routing scheme for $G$ as follows: for every vertex $v\in V$, its label
defined to be $\ell_{G}(v)=\left(\ell_{\rm crs}(\chi(v)),l_{\rm
dl}(\chi(v))\right)$, and its table $\tau_{G}(v)$ to be the concatenation of
$\left\\{\left(\tau_{\rm crs}(v^{\prime}),l_{\rm
dl}(v^{\prime})\right)\right\\}_{v^{\prime}\in f(v)}$. In words, the label
$\ell_{G}(v)$ consist of the routing label $\ell_{\rm crs}(\chi(v))$, and
distance label $l_{\rm dl}(\chi(v))$, of the chief $\chi(v)$ in $T$, while the
routing table $\tau_{G}(v)$ consist of the routing table $\tau_{\rm
crs}(v^{\prime})$, and distance label $l_{\rm dl}(v^{\prime})$, of all the
copies $v^{\prime}$ in the clan $f(v)$. Clearly, the size of the label is
$O(\log n)+O(1)=O(\log n)$, while the expected size of the routing table is
$\mathbb{E}[\sum_{v^{\prime}\in
f(v)}O(1)]=O(1)\cdot\mathbb{E}[|f(v)|]=O(n^{\frac{1}{k}})$.

Consider a node $v$ that wants so send a package to a node $u$, while
possessing the routing label $\ell_{G}(u)$ of $u$. $v$ will go over all the
copies $v^{\prime}\in f(v)$, and choose the copy $v_{u}$ that minimized the
estimated distance $\mathcal{A}\left(l_{\rm dl}(v^{\prime}),l_{\rm
dl}(\chi(u))\right)$. Then, using the routing table $\tau_{\rm crs}(v_{u})$ of
$v_{u}$, $v$ will make a routing decision and transfer the package to the
first vertex $z^{\prime}\in T$ on the shortest path from $v_{u}$ to $\chi(u)$
in $T$. $v$ will transfer this package with a header consisting of the label
of $u$ and the name of $z^{\prime}$. This somewhat longer routing decision
process occurs only when a delivery is initiated. In any other step, a node
$z$ receives a package with a header containing the routing label of the
destination $\ell_{G}(u)$ and a name of a copy $z^{\prime}\in f(z)$. Then $z$
uses the routing table $\tau_{\rm crs}(z^{\prime})$ of $z^{\prime}$ to make a
routing decision and transfer the package to the first vertex $q^{\prime}\in
T$ on the shortest path from $z^{\prime}$ to $\chi(u)$ in $T$. As previously,
$z$ will transfer the package with a header consisting of the label of $u$ and
the name of $q^{\prime}$. Clearly the size of the header is $O(\log n)$. Note
that other than the first decision, each decision is made in constant time
(while the first decision is made in expected $O(n^{\frac{1}{k}})$ time).
Finally, when routing a package starting at $v$ towards $u$, the path
corresponds exactly to a path in $T$ from a copy $v_{u}\in f(v)$ to $\chi(u)$.
The length of this path is bounded by

$\displaystyle d_{T}(v_{u},\chi(u))$
$\displaystyle\leq\mathcal{A}\left(l_{{\rm dl}}(v_{u}),l_{{\rm
dl}}(\chi(u))\right)=\min_{v^{\prime}\in f(v)}\mathcal{A}\left(l_{{\rm
dl}}(v^{\prime}),l_{{\rm dl}}(\chi(u))\right)$
$\displaystyle\leq\min_{v^{\prime}\in f(v)}2\cdot
d_{T}(v^{\prime},\chi(u))=O(k\log\log n)\cdot d_{G}(v,u)\leavevmode\nobreak\
.$

∎

## Acknowledgments

The authors are grateful to Philip Klein for suggesting the metric
$\rho$-dominating/independent set problems, which eventually led to this
project. We thank Vincent Cohen-Addad for useful conversations and for
pointing out the proof of Theorem 17 to the first author. The first author
would like to thank Alexandr Andoni for helpful discussions. The second author
would like to thank Michael Lampis for discussing dynamic programming
algorithms for metric independent set/dominating set on bounded treewidth
graphs.

## References

  * [ABLP90] B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg.  Improved routing strategies with succinct tables.  J. Algorithms, 11(3):307–341,  1990, doi:10.1016/0196-6774(90)90017-9.
  * [ACE+20] I. Abraham, S. Chechik, M. Elkin, A. Filtser, and O. Neiman.  Ramsey spanning trees and their applications.  ACM Trans. Algorithms, 16(2):19:1–19:21, 2020.  preliminary version published in SODA 2018, doi:10.1145/3371039.
  * [AFGN18] I. Abraham, A. Filtser, A. Gupta, and O. Neiman.  Metric embedding via shortest path decompositions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 952–963, 2018.  full version: https://arxiv.org/abs/1708.04073, doi:10.1145/3188745.3188808.
  * [AGG+19] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar.  Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs.  SIAM J. Comput., 48(3):1120–1145, 2019.  preliminary version published in STOC 2014, doi:10.1137/17M1112406.
  * [AGHP16] S. Alstrup, I. L. Gørtz, E. B. Halvorsen, and E. Porat.  Distance labeling schemes for trees.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 132:1–132:16,  2016, doi:10.4230/LIPIcs.ICALP.2016.132.
  * [AHK12] S. Arora, E. Hazan, and S. Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing, 8(1):121–164,  2012, doi:10.4086/toc.2012.v008a006.
  * [AHL02] N. Alon, S. Hoory, and N. Linial.  The moore bound for irregular graphs.  Graphs Comb., 18(1):53–57,  2002, doi:10.1007/s003730200002.
  * [AKPW95] N. Alon, R. M. Karp, D. Peleg, and D. B. West.  A graph-theoretic game and its application to the k-server problem.  SIAM J. Comput., 24(1):78–100, 1995.  preliminary version published in On-Line Algorithms 1991, doi:10.1137/S0097539792224474.
  * [AMS99] N. Alon, Y. Matias, and M. Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.  preliminary version published in STOC 1996, doi:10.1006/jcss.1997.1545.
  * [AN19] I. Abraham and O. Neiman.  Using petal-decompositions to build a low stretch spanning tree.  SIAM J. Comput., 48(2):227–248, 2019.  preliminary version published in STOC 2012, doi:10.1137/17M1115575.
  * [AP92] B. Awerbuch and D. Peleg.  Routing with polynomial communication-space tradeoff.  SIAM J. Discrete Mathematics, 5:151–162,  1992\.
  * [AS03] V. Athitsos and S. Sclaroff.  Database indexing methods for 3d hand pose estimation.  In Gesture-Based Communication in Human-Computer Interaction, 5th International Gesture Workshop, GW 2003, Genova, Italy, April 15-17, 2003, Selected Revised Papers, pages 288–299,  2003, doi:10.1007/978-3-540-24598-8\\_27.
  * [AST90] N. Alon, P. D. Seymour, and R. Thomas.  A separator theorem for graphs with an excluded minor and its applications.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 293–299,  1990, doi:10.1145/100216.100254.
  * [Bak94] B. S. Baker.  Approximation algorithms for NP-complete problems on planar graphs.  Journal of the ACM, 41(1):153–180, 1994.  preliminary version published in FOCS 1983, doi:10.1145/174644.174650.
  * [Bar96] Y. Bartal.  Probabilistic approximations of metric spaces and its algorithmic applications.  In 37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184–193,  1996, doi:10.1109/SFCS.1996.548477.
  * [Bar98] Y. Bartal.  On approximating arbitrary metrices by tree metrics.  In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161–168,  1998, doi:10.1145/276698.276725.
  * [Bar04] Y. Bartal.  Graph decomposition lemmas and their role in metric embedding methods.  In Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pages 89–97,  2004, doi:10.1007/978-3-540-30140-0\\_10.
  * [Bar11] Y. Bartal.  Lecture notes in metric embedding theory and its algorithmic applications, 2011.  URL: http://moodle.cs.huji.ac.il/cs10/file.php/67720/GM_Lecture6.pdf.
  * [Bar21] Y. Bartal.  Advances in metric ramsey theory and its applications.  CoRR, abs/2104.03484,  2021, arXiv:2104.03484.
  * [BBM06] Y. Bartal, B. Bollobás, and M. Mendel.  Ramsey-type theorems for metric spaces with applications to online problems.  J. Comput. Syst. Sci., 72(5):890–921, 2006.  Special Issue on FOCS 2001, doi:10.1016/j.jcss.2005.05.008.
  * [BCL+18] S. Bubeck, M. B. Cohen, Y. T. Lee, J. R. Lee, and A. Madry.  k-server via multiscale entropic regularization.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 3–16,  2018, doi:10.1145/3188745.3188798.
  * [Ben66] C. T. Benson.  Minimal regular graphs of girths eight and twelve.  Canadian Journal of Mathematics, 18:1091â€“1094,  1966, doi:10.4153/CJM-1966-109-8.
  * [BFM86] J. Bourgain, T. Figiel, and V. Milman.  On Hilbertian subsets of finite metric spaces.  Israel J. Math., 55(2):147–152,  1986, doi:10.1007/BF02801990.
  * [BFN19] Y. Bartal, N. Fandina, and O. Neiman.  Covering metric spaces by few trees.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 20:1–20:16,  2019, doi:10.4230/LIPIcs.ICALP.2019.20.
  * [BGS16] G. E. Blelloch, Y. Gu, and Y. Sun.  A new efficient construction on probabilistic tree embeddings.  CoRR, abs/1605.04651, 2016.  https://arxiv.org/abs/1605.04651, arXiv:1605.04651.
  * [BL16] G. Borradaile and H. Le.  Optimal dynamic program for r-domination problems over tree decompositions.  In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, pages 8:1–8:23,  2016, doi:10.4230/LIPIcs.IPEC.2016.8.
  * [BLMN05a] Y. Bartal, N. Linial, M. Mendel, and A. Naor.  On metric Ramsey-type dichotomies.  Journal of the London Mathematical Society, 71(2):289–303,  2005, doi:10.1112/S0024610704006155.
  * [BLMN05b] Y. Bartal, N. Linial, M. Mendel, and A. Naor.  Some low distortion metric ramsey problems.  Discret. Comput. Geom., 33(1):27–41,  2005, doi:10.1007/s00454-004-1100-z.
  * [BLW17] G. Borradaile, H. Le, and C. Wulff-Nilsen.  Minor-free graphs have light spanners.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS ’17, pages 767–778,  2017, doi:10.1109/FOCS.2017.76.
  * [BM04] Y. Bartal and M. Mendel.  Multiembedding of metric spaces.  SIAM J. Comput., 34(1):248–259, 2004.  preliminary version published in SODA 2003, doi:10.1137/S0097539703433122.
  * [Bou85] J. Bourgain.  On lipschitz embedding of finite metric spaces in hilbert space.  Israel Journal of Mathematics, 52(1-2):46–52,  1985, doi:10.1007/BF02776078.
  * [BR10] A. Babu and J. Radhakrishnan.  An entropy based proof of the moore bound for irregular graphs.  CoRR, abs/1011.1058,  2010, arXiv:1011.1058.
  * [CFKL20] V. Cohen-Addad, A. Filtser, P. N. Klein, and H. Le.  On light spanners, low-treewidth embeddings and efficient traversing in minor-free graphs.  CoRR, abs/2009.05039, 2020.  To appear in FOCS 2020,https://arxiv.org/abs/2009.05039, arXiv:2009.05039.
  * [CG04] D. E. Carroll and A. Goel.  Lower bounds for embedding into distributions over excluded minor graph families.  In Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pages 146–156,  2004, doi:10.1007/978-3-540-30140-0\\_15.
  * [CG12] T. H. Chan and A. Gupta.  Approximating TSP on metrics with bounded global growth.  SIAM J. Comput., 41(3):587–617, 2012.  preliminary version published in SODA 2008, doi:10.1137/090749396.
  * [Che13] S. Chechik.  Compact routing schemes with improved stretch.  In ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages 33–41,  2013, doi:10.1145/2484239.2484268.
  * [Che15] S. Chechik.  Approximate distance oracles with improved bounds.  In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1–10,  2015, doi:10.1145/2746539.2746562.
  * [CJLV08] A. Chakrabarti, A. Jaffe, J. R. Lee, and J. Vincent.  Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 761–770,  2008, doi:10.1109/FOCS.2008.79.
  * [CKM19] V. Cohen-Addad, P. N. Klein, and C. Mathieu.  Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics.  SIAM J. Comput., 48(2):644–667, 2019.  preliminary version published in FOCS 2016, doi:10.1137/17M112717X.
  * [Cow01] L. Cowen.  Compact routing with minimum stretch.  J. Algorithms, 38(1):170–183, 2001.  preliminary version published in SODA 1999, doi:10.1006/jagm.2000.1134.
  * [DFHT05] E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos.  Fixed-parameter algorithms for (_k_ , _r_)-center in planar graphs and map graphs.  ACM Trans. Algorithms, 1(1):33–47, 2005.  preliminary version published in ICALP 2003, doi:10.1145/1077464.1077468.
  * [DHK05] E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi.  Algorithmic graph minor theory: Decomposition, approximation, and coloring.  In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 637–646,  2005, doi:10.1109/SFCS.2005.14.
  * [EEST08] M. Elkin, Y. Emek, D. A. Spielman, and S. Teng.  Lower-stretch spanning trees.  SIAM J. Comput., 38(2):608–628, 2008.  preliminary version published in STOC 2005, doi:10.1137/050641661.
  * [EFN18] M. Elkin, A. Filtser, and O. Neiman.  Prioritized metric structures and embedding.  SIAM J. Comput., 47(3):829–858, 2018.  preliminary version published in STOC 2015, doi:10.1137/17M1118749.
  * [EGP03] T. Eilam, C. Gavoille, and D. Peleg.  Compact routing schemes with low stretch factor.  J. Algorithms, 46(2):97–114, 2003.  preliminary version published in PODC 1998, doi:10.1016/S0196-6774(03)00002-6.
  * [EILM16] H. Eto, T. Ito, Z. Liu, and E. Miyano.  Approximability of the distance independent set problem on regular graphs and planar graphs.  In Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings, pages 270–284,  2016, doi:10.1007/978-3-319-48749-6\\_20.
  * [EKM14] D. Eisenstat, P. N. Klein, and C. Mathieu.  Approximating _k_ -center in planar graphs.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 617–627,  2014, doi:10.1137/1.9781611973402.47.
  * [EN19] M. Elkin and O. Neiman.  Efficient algorithms for constructing very sparse spanners and emulators.  ACM Trans. Algorithms, 15(1):4:1–4:29, 2019.  preliminary version published in SODA 2017, doi:10.1145/3274651.
  * [FFKP18] A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post.  A (1+$\epsilon$)-embedding of low highway dimension graphs into bounded treewidth graphs.  SIAM J. Comput., 47(4):1667–1704, 2018.  preliminary version published in ICALP 2015, doi:10.1137/16M1067196.
  * [FGK20] A. Filtser, L. Gottlieb, and R. Krauthgamer.  Labelings vs. embeddings: On distributed representations of distances.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1063–1075,  2020, doi:10.1137/1.9781611975994.65.
  * [FGNW17] O. Freedman, P. Gawrychowski, P. K. Nicholson, and O. Weimann.  Optimal distance labeling schemes for trees.  In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 185–194,  2017, doi:10.1145/3087801.3087804.
  * [Fil19] A. Filtser.  On strong diameter padded decompositions.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 6:1–6:21,  2019, doi:10.4230/LIPIcs.APPROX-RANDOM.2019.6.
  * [FKS19] E. Fox-Epstein, P. N. Klein, and A. Schild.  Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ‘19, page 1069–1088,  2019, doi:10.1137/1.9781611975482.66.
  * [FL21] A. Filtser and H. Le.  Reliable spanners: Locality-sensitive orderings strike back.  CoRR, abs/2101.07428,  2021, arXiv:2101.07428.
  * [Fre87] G. N. Frederickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM J. Comput., 16(6):1004–1022,  1987, doi:10.1137/0216064.
  * [FRT04] J. Fakcharoenphol, S. Rao, and K. Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, November 2004.  preliminary version published in STOC 2003, doi:10.1016/j.jcss.2004.04.011.
  * [GKK+01] C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg.  Approximate distance labeling schemes.  In Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, pages 476–487,  2001, doi:10.1007/3-540-44676-1\\_40.
  * [GKK17] L. Gottlieb, A. Kontorovich, and R. Krauthgamer.  Efficient regression in metric spaces via approximate lipschitz extension.  IEEE Trans. Inf. Theory, 63(8):4838–4849, 2017.  preliminary version published in SIMBAD 2013, doi:10.1109/TIT.2017.2713820.
  * [GPPR04] C. Gavoille, D. Peleg, S. Pérennes, and R. Raz.  Distance labeling in graphs.  J. Algorithms, 53(1):85–112, 2004.  preliminary version published in SODA 2001, doi:10.1016/j.jalgor.2004.05.002.
  * [HBK+03] E. Halperin, J. Buhler, R. M. Karp, R. Krauthgamer, and B. Westover.  Detecting protein sequence conservation via metric embeddings.  Bioinformatics, 19(suppl 1):i122–i129,  07 2003, arXiv:https://academic.oup.com/bioinformatics/article-pdf/19/suppl\\_1/i122/614436/btg1016.pdf, doi:10.1093/bioinformatics/btg1016.
  * [HHZ21] B. Haeupler, D. E. Hershkowitz, and G. Zuzic.  Deterministic tree embeddings with copies for algorithms against adaptive adversaries.  CoRR, abs/2102.05168,  2021, arXiv:2102.05168.
  * [Ind01] P. Indyk.  Algorithmic applications of low-distortion geometric embeddings.  In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 10–33,  2001, doi:10.1109/SFCS.2001.959878.
  * [Jor69] C. Jordan.  Sur les assemblages de lignes.  Journal für die reine und angewandte Mathematik, 70:185–190,  1869\.
  * [Kar89] R. M. Karp.  A 2k-competitive algorithm for the circle.  Manuscript, August, 5,  1989\.
  * [KKM+12] M. Khan, F. Kuhn, D. Malkhi, G. Pandurangan, and K. Talwar.  Efficient distributed approximation algorithms via probabilistic tree embeddings.  Distributed Comput., 25(3):189–205, 2012.  preliminary version published in PODC 2008, doi:10.1007/s00446-012-0157-9.
  * [KLMN05] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor.  Measured descent: a new embedding method for finite metrics.  Geometric and Functional Analysis, 15(4):839–858, 2005.  preliminary version published in FOCS 2004, doi:10.1007/s00039-005-0527-6.
  * [KLP19] I. Katsikarelis, M. Lampis, and V. T. Paschos.  Structural parameters, tight bounds, and approximation for (k, r)-center.  Discret. Appl. Math., 264:90–117, 2019.  preliminary version published in ISAAC 2017, doi:10.1016/j.dam.2018.11.002.
  * [KLP20] I. Katsikarelis, M. Lampis, and V. T. Paschos.  Structurally parameterized d-scattered set.  Discrete Applied Mathematics, 2020.  preliminary version published in WG 2018, doi:10.1016/j.dam.2020.03.052.
  * [Le18] H. Le.  Structural Results and Approximation Algorithms in Minor-free Graphs.  PhD thesis, Oregon State University,  2018\.
  * [Lem03] A. Lemin.  On ultrametrization of general metric spaces.  Proceedings of the American mathematical society, 131(3):979–989,  2003, doi:10.1090/S0002-9939-02-06605-4.
  * [LLR95] N. Linial, E. London, and Y. Rabinovich.  The geometry of graphs and some of its algorithmic applications.  Comb., 15(2):215–245, 1995.  preliminary version published in FOCS 1994, doi:10.1007/BF01200757.
  * [LUW95] F. Lazebnik, V. A. Ustimenko, and A. J. Woldar.  A new series of dense graphs of high girth.  Bulletin of the American mathematical society, 32(1):73–79,  1995, doi:10.1090/S0273-0979-1995-00569-0.
  * [MN07] M. Mendel and A. Naor.  Ramsey partitions and proximity data structures.  Journal of the European Mathematical Society, 9(2):253–275, 2007\.  preliminary version published in FOCS 2006, doi:10.4171/JEMS/79.
  * [MP15] D. Marx and M. Pilipczuk.  Optimal parameterized algorithms for planar facility location problems using voronoi diagrams.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 865–877,  2015, doi:10.1007/978-3-662-48350-3\\_72.
  * [NT12] A. Naor and T. Tao.  Scale-oblivious metric fragmentation and the nonlinear dvoretzky theorem.  Israel Journal of Mathematics, 192(1):489–504,  2012, doi:10.1007/s11856-012-0039-7.
  * [Pel00] D. Peleg.  Proximity-preserving labeling schemes.  J. Graph Theory, 33(3):167–176, 2000.  preliminary version published in WG 1999, doi:10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5.
  * [PU89] D. Peleg and E. Upfal.  A trade-off between space and efficiency for routing tables.  J. ACM, 36(3):510–530,  1989, doi:10.1145/65950.65953.
  * [Rao99] S. Rao.  Small distortion and volume preserving embeddings for planar and Euclidean metrics.  In Proceedings of the Fifteenth Annual Symposium on Computational Geometry, Miami Beach, Florida, USA, June 13-16, 1999, pages 300–306,  1999, doi:10.1145/304893.304983.
  * [RR98] Y. Rabinovich and R. Raz.  Lower bounds on the distortion of embedding finite metric spaces in graphs.  Discret. Comput. Geom., 19(1):79–94,  1998, doi:10.1007/PL00009336.
  * [RS03] N. Robertson and P. D. Seymour.  Graph minors. XVI. Excluding a non-planar graph.  Journal of Combinatoral Theory Series B, 89(1):43–76,  2003, doi:10.1016/S0095-8956(03)00042-X.
  * [Tal04] K. Talwar.  Bypassing the embedding: algorithms for low dimensional metrics.  In STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 281–290. ACM Press,  2004, doi:http://doi.acm.org/10.1145/1007352.1007399.
  * [TZ01] M. Thorup and U. Zwick.  Compact routing schemes.  In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001, pages 1–10,  2001, doi:10.1145/378580.378581.
  * [TZ05] M. Thorup and U. Zwick.  Approximate distance oracles.  J. ACM, 52(1):1–24,  2005, doi:10.1145/1044731.1044732.
  * [Wen91] R. Wenger.  Extremal graphs with no c4’s, c6’s, or c10’s.  Journal of Combinatorial Theory, Series B, 52(1):113 – 116,  1991, doi:https://doi.org/10.1016/0095-8956(91)90097-4.

##  Appendix A Path Distortion of Clan embeddings into ultrametrics

In this section we provide briefly the modification and missing details
required to obtain the path distortion property for our clan embedding into
ultrametrics.

######  Definition 10 (Path-distortion).

We say that the one-to-many embedding $f:X\rightarrow 2^{Y}$ between
$(X,d_{X})$ to $(Y,d_{Y})$ has _path-distortion_ $t$ if for every sequence
$\left(x_{0},x_{1},\dots,x_{m}\right)$ in $X$ there is a sequence
$v^{\prime}_{0},\dots,v^{\prime}_{m}$ in $Y$ where $x^{\prime}_{i}\in
f(x_{i})$, such that
$\sum_{i=0}^{m-1}d_{Y}(x^{\prime}_{i},x^{\prime}_{i+1})\leq
t\cdot\sum_{i=1}^{m-1}d_{X}(x_{i},x_{i+1})$.

To obtain a clan embedding $(f,\chi)$ as in Lemma 2, the only modification
required is to use the following strengthen version of 1 (the proof of which
appears bellow).

######  Claim 3.

There is a point $v\in X$ and radius $R\in(0,\frac{\mathrm{diam}(X)}{2}]$,
such that the sets ${P=B_{X}(v,R+\frac{1}{8(k+1)}\cdot\mathrm{diam}(X))}$,
$Q=B_{X}(v,R)$, and $\bar{Q}=X\setminus Q$ satisfy the following properties:

  1. 1.

$\min\\{\mu(P),\mu(\bar{Q})\\}\leq\frac{2}{3}\cdot\mu(X)$, and
$\mathrm{diam}(P)\leq\frac{1}{2}\cdot\mathrm{diam}(X)$.

  2. 2.

$\mu(P)\leq\mu(Q)\cdot\left(\frac{\mu^{*}(X)}{\mu^{*}(P)}\right)^{\frac{1}{k}}$.

As a result, the distortion gurantee we will obtain will be $16(k+1)$ instead
of $16k$. However, we will be guaranteed that recursively one of the two
created clusters has measure at most $\frac{2}{3}\mu(X)$, and also that the
diameter in the first cluster is bounded by half the diameter of $X$. These
are the only properties used in the proof of [BM04] to obtain the path
distortion gurantee. In particular, the exact same argument as in [BM04] will
imply the following result:

######  Lemma 20.

Given an $n$-point metric space $(X,d_{X})$ with aspect
ratio${}^{\ref{foot:aspectRatio}}$ $\Phi$, $(\geq 1)$-measure
$\mu:X\rightarrow\mathbb{R}_{\geq 1}$, and integer parameter $k\geq 1$, there
is a clan embedding $(f,\chi)$ into an ultrametric with multiplicative
distortion $16(k+1)$, path distortion $O(k)\cdot\min\\{\log n,\log\Phi\\}$,
and such that $\mathbb{E}_{x\sim\mu}[|f(x)|]\leq\mu(X)^{1+\frac{1}{k}}$.

Using the exact same arguments we had to obtain Theorem 1 from Lemma 2, we
conclude:

######  Theorem 15 (Clan embedding into ultrametric).

Given an $n$-point metric space $(X,d_{X})$ with aspect ration $\Phi$, and
parameter $\epsilon\in(0,1]$, there is a uniform distribution $\mathcal{D}$
over $O(n\log n/\epsilon^{2})$ clan embeddings $(f,\chi)$ into ulrametrics
with multiplicative distortion $O(\frac{\log n}{\epsilon})$, path distortion
$O(\frac{\log n}{\epsilon})\cdot\min\\{\log n,\log\Phi\\}$, and such that for
every point $x\in X$, $\mathbb{E}_{f\sim\mathcal{D}}[|f(x)|]\leq 1+\epsilon$.

In addition, for every $k\in\mathbb{N}$, there is a uniform distribution
$\mathcal{D}$ over $O(n^{1+\frac{2}{k}}\log n)$ clan embeddings $(f,\chi)$
into ulrametrics with multiplicative distortion $16(k+1)$, path distortion
$O(k)\cdot\min\\{\log n,\log\Phi\\}$, and such that for every point $x\in X$,
$\mathbb{E}_{f\sim\mathcal{D}}[|f(x)|]=O(n^{\frac{1}{k}})$.

######  Remark 6.

The spanning clan embedding construction for Theorem 3 actually provides path-
distortion gurantee without modification. This is as in the create-petal
procedure (Algorithm 3), we always create a petal (cluster) with measure at
most $\frac{1}{2}\mu(Y)$ (and bounded radius).

###### Proof of 3.

Let $v$ be the point minimizing the ratio
$\frac{\mu\left(B_{X}(v,\frac{\mathrm{diam}(X)}{4})\right)}{\mu\left(B_{X}(v,\frac{\mathrm{diam}(X)}{8})\right)}$.
Set $\rho=\frac{\mathrm{diam}(X)}{8(k+1)}$, and for $i\in[0,k]$ let
$Q_{i}=B_{X}(v,\frac{\mathrm{diam}(X)}{8}+i\cdot\rho)$. Let
$i^{\prime}\in[0,k-1]$ be the index minimizing
$\frac{\mu(Q_{i+1})}{\mu(Q_{i})}$. Then,

$\left(\frac{\mu(Q_{k+1})}{\mu(Q_{0})}\right)^{\frac{1}{k}}\geq\left(\frac{\mu(Q_{k})}{\mu(Q_{0})}\right)^{\frac{1}{k}}=\left(\frac{\mu(Q_{1})}{\mu(Q_{0})}\cdot\frac{\mu(Q_{2})}{\mu(Q_{1})}\cdots\frac{\mu(Q_{k})}{\mu(Q_{k-1})}\right)^{\frac{1}{k}}\geq\left(\frac{\mu(Q_{i^{\prime}+1})}{\mu(Q_{i^{\prime}})}\right)^{k\cdot\frac{1}{k}}=\frac{\mu(Q_{i^{\prime}+1})}{\mu(Q_{i^{\prime}})}\leavevmode\nobreak\
.$

If $\mu(Q_{i^{\prime}+1})\leq\frac{2}{3}\mu(X)$ or
$\mu(Q_{i^{\prime}})\geq\frac{1}{3}\mu(X)$, fix $i=i^{\prime}$. Otherwise, fix
$i=i^{\prime}+1$. Note that $i\in[0,k]$. Set
$R=\frac{\mathrm{diam}(X)}{8}+i\cdot\rho$, and $P=B_{X}(v,R+\rho)$,
$Q=B_{X}(v,R)$, $\bar{Q}=X\setminus Q$. Note that $\mathrm{diam}(P)\leq
2\cdot(\frac{\mathrm{diam}(X)}{8}+(k+1)\cdot\rho)=\frac{\mathrm{diam}(X)}{2}$.

If $i=i^{\prime}$, then clearly
$\frac{\mu(P)}{\mu(Q)}\leq\left(\frac{\mu(Q_{k+1})}{\mu(Q_{0})}\right)^{\frac{1}{k}}$
and $\min\\{\mu(P),\mu(\bar{Q})\\}\leq\frac{2}{3}\cdot\mu(X)$. Otherwise,
$i=i^{\prime}+1$, thus $\mu(Q_{i^{\prime}+1})>\frac{2}{3}\mu(X)$ and
$\mu(Q_{i^{\prime}})<\frac{1}{3}\mu(X)$, implying that
$\frac{\mu(Q_{i^{\prime}+1})}{\mu(Q_{i^{\prime}})}>2$ and thus

$\frac{\mu(P)}{\mu(Q)}=\frac{\mu(Q_{i+1})}{\mu(Q_{i})}=\frac{\mu(Q_{i^{\prime}+2})}{\mu(Q_{i^{\prime}+1})}\leq\frac{\mu(X)}{\frac{2}{3}\mu(X)}=\frac{3}{2}<\frac{\mu(Q_{i^{\prime}+1})}{\mu(Q_{i^{\prime}})}\leq\left(\frac{\mu(Q_{k+1})}{\mu(Q_{0})}\right)^{\frac{1}{k}}\leavevmode\nobreak\
.$

Furthermore, $\mu(\bar{Q})=\mu(X)-\mu(Q_{i^{\prime}+1})<\frac{1}{3}\mu(X)$. In
both cases we obtain that
$\min\\{\mu(P),\mu(\bar{Q})\\}\leq\frac{2}{3}\cdot\mu(X)$ and
$\frac{\mu(P)}{\mu(Q)}\leq\left(\frac{\mu(Q_{k+1})}{\mu(Q_{0})}\right)^{\frac{1}{k}}$.
It remains to prove the second required property.

Let $u_{P}$ be the point defining $\mu^{*}(P)$, that is
$\mu^{*}(P)=\mu\left(B_{P}(u_{P},\frac{\mathrm{diam}(P)}{4}\right)\leq\mu\left(B_{P}(u_{P},\frac{\mathrm{diam}(X)}{8}\right)$.
Using the minimality of $v$, it holds that

$\frac{\mu(P)}{\mu(Q)}\leq\left(\frac{\mu(Q_{k})}{\mu(Q_{0})}\right)^{\frac{1}{k}}=\left(\frac{\mu\left(B_{X}(v,\frac{\mathrm{diam}(X)}{4})\right)}{\mu\left(B_{X}(v,\frac{\mathrm{diam}(X)}{8})\right)}\right)^{\frac{1}{k}}\stackrel{{\scriptstyle(*)}}{{\leq}}\left(\frac{\mu\left(B_{X}(u_{P},\frac{\mathrm{diam}(X)}{4})\right)}{\mu\left(B_{X}(u_{P},\frac{\mathrm{diam}(X)}{8})\right)}\right)^{\frac{1}{k}}\leq\left(\frac{\mu^{*}\left(X\right)}{\mu^{*}\left(P\right)}\right)^{\frac{1}{k}}\leavevmode\nobreak\
.$

where $(*)$ is due to the choice of $v$. ∎

##  Appendix B Local Search Algorithms for Metric Becker Problems

In this section we present PTAS’s ${}^{\ref{foot:approximationSchemes}}$ for
the metric $\rho$-dominating/independent set problems under the uniform
measure. Both algorithms are local search algorithms. The analysis of the
algorithm for the metric $\rho$-dominating set problem was presented in
[Le18]. This analysis uses techniques similar to the ones used in [CKM19] to
construct PTAS for the $k$-means and $k$-median problems in minor-free graphs.
The analysis for the metric $\rho$-independent set problem is original (even
though similar).

In both proofs we will use $r$-divisions. The following theorem follows from
[Fre87, AST90] (see [CKM19] for details).

######  Theorem 16 ([Fre87, AST90]).

For every graph $H$, there is an absolute constant $c_{H}$ such that every
$r\in\mathbb{N}$, and every $n$-vertex $H$-minor-free graph $G=(V,E)$, the
vertices of $G$ can be divided into clusters $\mathcal{R}$ such that:

  1. 1.

For every edge $\\{u,v\\}\in E$, there is a cluster $C\in\mathcal{R}$ such
that $u,v\in C$.

  2. 2.

For every $C\in\mathcal{R}$, $|C|\leq r^{2}$.

  3. 3.

Let $\mathcal{B}$ be the set of vertices appearing in more than a single
cluster, called boundary vertices, then
$\sum_{C\in\mathcal{R}}|C\cap\mathcal{B}|\leq c_{H}\cdot\frac{n}{r}$.

###  B.1 Local search for $\rho$-dominating set under uniform measure

We state and prove the theorem here when the set of terminals $\mathcal{K}=V$,
however it can be easily accommodated to deal with a general terminal set.

######  Theorem 17.

There is a polynomial approximation scheme (PTAS) for the metric
$\rho$-dominating set problem in $H$-minor-free graphs under the uniform
measure.
Specifically, given a weighted $n$-vertex $H$-minor-free graph $G=(V,E,w)$,
and parameters $\epsilon\in(0,\frac{1}{2})$, $\rho>0$, in
$n^{O_{|H|}(\epsilon^{-2})}$ time, one can find a $\rho$-dominating set
$S\subseteq V$ such that for every $\rho$-dominating set $\tilde{S}$,
$|S|\leq(1+\epsilon)|\tilde{S}|$.

input : $n$ vertex graph $G=(V,E,w)$, parameters $\rho,s$

output : $\rho$-dominating set $S$

1 $S\leftarrow V$

2 while  _$\exists$ $\rho$-dominating set $S^{\prime}\subseteq V$ s.t.
$|S^{\prime}|<|S|$ and $|S\setminus S^{\prime}|+|S^{\prime}\setminus S|\leq
s$_ do

3 $S\leftarrow S^{\prime}$

4

5

6return $S$

Algorithm 4 Local search algorithm for metric $\rho$-dominating set

_Proof._ Set $r=\frac{4c_{H}}{\epsilon}$ where $c_{H}$ is the constant from
Theorem 16 w.r.t. $H$. Let $S$ be the set returned by the local search
Algorithm 4 with parameters $\rho$, and
$s=r^{2}=O_{H}(\frac{1}{\epsilon^{2}})$. Clearly $S$ is a $\rho$-dominating
set. The running time of each step of the while loop is at most ${n\choose
s}^{2}\cdot\mathrm{poly}(n)=n^{O_{|H|}(\epsilon^{-2})}$, as there are at most
$n$ iterations, the running time follows. Let $S_{\mathrm{opt}}$ be the
$\rho$-dominating set of minimum cardinality, it remains to prove that
$|S|\leq(1+\epsilon)|S_{\mathrm{opt}}|$.

Let $\tilde{V}=S\cup S_{\mathrm{opt}}$, and let $\mathcal{P}$ be a partition
of the vertices in $V$ w.r.t. the Voronoi cells with $\tilde{V}$ as centers.
Specifically, for each vertex $u\in V$, $u$ joins the cluster $P_{v}$ of a
vertex $v\in\tilde{V}$ at minimal distance $\min_{v\in\tilde{V}}d_{G}(u,v)$.
141414For simplicity, we will assume that all the pairwise distances are
unique. Alternatively, one can break ties in a consistent way (i.e. w.r.t.
some total order). Let $\tilde{G}$ be the graph obtained from $G$ by
contracting the internal edges in each Voronoi cell (and keeping only a single
copy of each edge). Alternatively, one can define $\tilde{G}$ with $\tilde{V}$
as vertex set such that $v,u\in\tilde{V}$ are adjacent iff there is an edge in
$G$ between a vertex in $P_{u}$ to a vertex in $P_{v}$. Note that $\tilde{G}$
is a minor of $G$, and hence is $H$-minor-free.

Next, we use Theorem 16 on $\tilde{G}$ to obtain $r$-division $\mathcal{R}$,
with $\mathcal{B}$ as boundary vertices. Consider a cluster $C\in\mathcal{R}$,
and let $C^{\prime}=C\cap(\mathcal{B}\cup S_{\mathrm{opt}})$. Fix
$S^{\prime}=(S\setminus C)\cup C^{\prime}$.

######  Claim 4.

$S^{\prime}$ is a $\rho$-dominating set.

_Proof._ Consider a vertex $u\in V$, We will argue that $u$ is at distance at
most $\rho$ from some vertex in $S^{\prime}$. Let $v_{1}\in S$ (resp.
$v_{2}\in S_{\mathrm{opt}}$) be the closest vertex to $u$ in $S$ (resp. in
$S_{\mathrm{opt}}$). It holds that $d_{G}(u,v_{1}),d_{G}(u,v_{2})\leq\rho$. If
either $v_{1}\notin C$, $v_{1}\in C\cap\mathcal{B}$, or $v_{2}\in C$ then
$S^{\prime}$ contains at least one of $v_{1},v_{2}$ and we are done. Thus we
can assume that $v_{1}\in C\setminus\mathcal{B}$ and $v_{2}\notin C$. Let
$\Pi=\\{v_{1}=z_{0},z_{1},\dots,z_{a},u,w_{0},w_{1},\dots,w_{b}=v_{2}\\}$ be
the unique shortest path from $v_{1}$ to $v_{2}$ that goes through $u$ (the
thick black line in illustration on the right).

Assume first that $u$ belongs to the Voroni cell $P_{v_{1}}$ of $v_{1}$
(encircled by a blue dashed line). For every $i$ and $v^{\prime}\in\tilde{V}$
it holds that $d_{G}(v^{\prime},z_{i})\geq
d_{G}(v^{\prime},u)-d_{G}(u,z_{i})>d_{G}(v_{1},u)-d_{G}(u,z_{i})=d_{G}(v_{1},z_{i})$.
It follows that all the vertices $\\{z_{0},z_{1},\dots,z_{a}\\}$ belong to the
Voronoi cell $P_{v_{1}}$. As $v_{1}\in C\setminus\mathcal{B}$, and
$v_{2}\notin C$, there must be some index $j$ such that $w_{j}$ belongs to the
Voronoi cell $P_{v_{3}}$ of $v_{3}\in C\cap\mathcal{B}$ (as otherwise there
will be an edge in $\tilde{G}$ between a vertex in $C\setminus\mathcal{B}$ to
a vertex not in $C$). It holds that

$d_{G}(u,v_{3})\leq d_{G}(u,w_{j})+d_{G}(w_{j},v_{3})\leq
d_{G}(u,w_{j})+d_{G}(w_{j},v_{2})=d_{G}(u,v_{2})\leq\rho\leavevmode\nobreak\
,$

where the first inequality follows by triangle inequality, the second as
$w_{j}\in P_{v_{3}}$, and the equality as $w_{j}$ lays on the shortest path
from $u$ to $v_{2}$. As $v_{3}\in C\cap\mathcal{B}$ it follows that $v_{3}\in
S^{\prime}$, thus we are done. The case $u\in P_{v_{2}}$ is symmetric. ∎

It holds that $|S^{\prime}\setminus S|+|S\setminus S^{\prime}|\leq|C|\leq
r^{2}=s$. Thus, $|S^{\prime}|\geq|S|$ since otherwise, Algorithm 4 would’ve
not returned the set $S$. Hence $|C\cap(\mathcal{B}\cup
S_{\mathrm{opt}})|=|C^{\prime}|\geq|C\cap S|$. As the same argument could be
applied on every cluster $C\in\mathcal{R}$, we conclude that,

$|S|=\sum_{C\in\mathcal{R}}|C\cap
S|\leq\sum_{C\in\mathcal{R}}|C\cap(\mathcal{B}\cup
S_{\mathrm{opt}})|\leq|S_{\mathrm{opt}}|+\sum_{C\in\mathcal{R}}|C\cap\mathcal{B}|\leq|S_{\mathrm{opt}}|+c_{H}\cdot\frac{|\tilde{V}|}{r}\leq|S_{\mathrm{opt}}|+2c_{H}\cdot\frac{|S|}{r}\leavevmode\nobreak\
.$

But this implies
$|S_{\mathrm{opt}}|\geq(1-\frac{2c_{H}}{r})|S|=(1-\frac{\epsilon}{2})|S|$,
thus
$|S|\leq\frac{1}{1-\frac{\epsilon}{2}}|S_{\mathrm{opt}}|\leq(1+\epsilon)|S_{\mathrm{opt}}|$.
∎

###  B.2 Local search for $\rho$-independent set under uniform measure

######  Theorem 18.

There is a polynomial approximation scheme (PTAS) for the metric
$\rho$-independent set problem in $H$-minor-free graphs under uniform measure.
Specifically, given a weighted $n$-vertex $H$-minor-free graph $G=(V,E,w)$,
and parameters $\epsilon\in(0,\frac{1}{2})$, $\rho>0$, in
$n^{O_{|H|}(\epsilon^{-2})}$ time, one can find a $\rho$-independent set
$S\subseteq V$ such that for every $\rho$-independent set $\tilde{S}$,
$|S|\geq(1-\epsilon)|\tilde{S}|$.

input : $n$ vertex graph $G=(V,E,w)$, parameters $\rho,s$

output : $\rho$-independent set $S$

1 $S\leftarrow\emptyset$

2 while  _$\exists$ $\rho$-independent set $S^{\prime}\subseteq V$ s.t.
$|S^{\prime}|>|S|$ and $|S\setminus S^{\prime}|+|S^{\prime}\setminus S|\leq
s$_ do

3 $S\leftarrow S^{\prime}$

4

5

6return $S$

Algorithm 5 Local search algorithm for metric $\rho$-independent set

###### Proof.

Set $r=\frac{4c_{H}}{\epsilon}$ where $c_{H}$ is the constant from Theorem 16
w.r.t. $H$. Let $S$ be the set returned by the local search Algorithm 5 with
parameters $\rho$, and
$s=r^{2}=\frac{16c_{H}^{2}}{\epsilon^{2}}=O_{H}(\frac{1}{\epsilon^{2}})$.
Clearly $S$ is a $\rho$-independent set. The running time of each step of the
while loop is at most ${n\choose
s}^{2}\cdot\mathrm{poly}(n)=n^{O_{|H|}(\epsilon^{-2})}$, as there are at most
$n$ iterations, the running time follows. Let $S_{\mathrm{opt}}$ be the
$\rho$-independent set of maximum cardinality, it remains to prove that
$|S|\geq(1-\epsilon)|S_{\mathrm{opt}}|$.

Construct a graph $\tilde{G}$ with $\tilde{V}=S\cup S_{\mathrm{opt}}$ as a
vertex set. We add an edge an edge between $u,v\in\tilde{V}$ iff
$d_{G}(u,v)<\rho$. Clearly all the edges are from $S\times S_{\mathrm{opt}}$
(as both $S,S_{\mathrm{opt}}$ are $\rho$-independent sets). Note that
$\tilde{V}$ is a minor of $G$. This is because if we take all the shortest
paths $P_{u,v}$ for $\\{u,v\\}\in E^{\prime}$ they will not intersect. To see
this, assume for contradiction that there are different pairs $u,u^{\prime}\in
S_{\mathrm{opt}}$ , $v,v^{\prime}\in S$ such that
$\\{u,v\\},\\{u^{\prime},v^{\prime}\\}\in E$, and there is some vertex $z$
such that $z\in P_{u,v}\cap P_{u^{\prime},v^{\prime}}$. W.l.o.g. assume that
$d_{G}(u,z)+d_{G}(u^{\prime},z)\leq d_{G}(z,v)+d_{G}(z,v^{\prime})$. Using the
triangle inequality it follows that

$\displaystyle d_{G}(u,u^{\prime})\leq d_{G}(u,z)+d_{G}(u^{\prime},z)$
$\displaystyle\leq\frac{1}{2}\cdot\left(d_{G}(u,z)+d_{G}(z,v)+d_{G}(u^{\prime},z)+d_{G}(z,v^{\prime})\right)$
$\displaystyle=\frac{1}{2}\cdot\left(d_{G}(u,v)+d_{G}(u^{\prime},v^{\prime})\right)<\rho\leavevmode\nobreak\
,$

a contradiction.

Next, we apply Theorem 16 to $\tilde{G}$ to obtain $r$-division $\mathcal{R}$,
with $\mathcal{B}$ as boundary vertices. Consider a cluster $C\in\mathcal{R}$,
and let $C^{\prime}=(C\cap S_{\mathrm{opt}})\setminus\mathcal{B}$. Fix
$S^{\prime}=(S\setminus C)\cup C^{\prime}$.

######  Claim 5.

$S^{\prime}$ is a $\rho$-independent set.

###### Proof.

Consider a pair of vertices $u,v\in S^{\prime}$, we will show that
$d_{G}(u,v)\geq\rho$. If both $u,v$ belong to $S$, then since $S$ is a
$\rho$-independent set, it follows that $d_{G}(u,v)\geq\rho$. The same
argument holds if both $u,v$ belong to $S_{\mathrm{opt}}$. We thus can assume
w.l.o.g. that $u\in S\setminus S_{\mathrm{opt}}$ and $v\in
S_{\mathrm{opt}}\setminus S$. It follows that $u\notin C$ while $v\in C$.
However, as $v\in C\cap S^{\prime}$, necessarily $v\notin\mathcal{B}$. The
only vertices in $C$ with edges towards vertices out of $C$ are in
$\mathcal{B}$. It follows that $\\{u,v\\}$ is not an edge of $\tilde{G}$,
implying $d_{G}(u,v)\geq\rho$. ∎

It holds that $|S^{\prime}\setminus S|+|S\setminus S^{\prime}|\leq|C|\leq
r^{2}=s$. Thus, $|S^{\prime}|\leq|S|$, as otherwise Algorithm 5 would have not
returned the set $S$. Hence, $|(C\cap
S_{\mathrm{opt}})\setminus\mathcal{B}|=|C^{\prime}|\leq|C\cap S|$. As the same
argument could be applied on every cluster $C\in\mathcal{R}$, we conclude
that,

$|S|=\sum_{C\in\mathcal{R}}|C\cap S|\geq\sum_{C\in\mathcal{R}}|(C\cap
S_{\mathrm{opt}})\setminus\mathcal{B}|\geq|S_{\mathrm{opt}}|-\sum_{C\in\mathcal{R}}|C\cap\mathcal{B}|\geq|S_{\mathrm{opt}}|-c_{H}\cdot\frac{|\tilde{V}|}{r}\geq|S_{\mathrm{opt}}|-2c_{H}\cdot\frac{|S|}{r}\leavevmode\nobreak\
.$

But this implies that
$|S_{\mathrm{opt}}|\leq(1+\frac{2c_{H}}{r})|S|=(1+\frac{\epsilon}{2})|S|$,
thus
$|S|\geq\frac{1}{1+\frac{\epsilon}{2}}|S_{\mathrm{opt}}|\geq(1-\epsilon)|S_{\mathrm{opt}}|$.
∎