# Clan Embeddings into Trees, and Low Treewidth Graphs

Arnold Filtser The research was supported by the Simons Foundation. Columbia
University<EMAIL_ADDRESS>Hung Le The research was supported by the
start-up grant of UMass Amherst. University of Massachusetts at Amherst,
<EMAIL_ADDRESS>
###### Abstract

In low distortion metric embeddings, the goal is to embed a host “hard” metric
space into a “simpler” target space while approximately preserving pairwise
distances. A highly desirable target space is that of a tree metric.
Unfortunately, such embedding will result in a huge distortion. A celebrated
bypass to this problem is stochastic embedding with logarithmic expected
distortion. Another bypass is Ramsey-type embedding, where the distortion
guarantee applies only to a subset of the points. However, both these
solutions fail to provide an embedding into a single tree with a worst-case
distortion guarantee on all pairs. In this paper, we propose a novel third
bypass called _clan embedding_. Here each point $x$ is mapped to a subset of
points $f(x)$, called a _clan_ , with a special _chief_ point $\chi(x)\in
f(x)$. The clan embedding has multiplicative distortion $t$ if for every pair
$(x,y)$ some copy $y^{\prime}\in f(y)$ in the clan of $y$ is close to the
chief of $x$: $\min_{y^{\prime}\in f(y)}d(y^{\prime},\chi(x))\leq t\cdot
d(x,y)$. Our first result is a clan embedding into a tree with multiplicative
distortion $O(\frac{\log n}{\epsilon})$ such that each point has $1+\epsilon$
copies (in expectation). In addition, we provide a “spanning” version of this
theorem for graphs and use it to devise the first compact routing scheme with
constant size routing tables.

We then focus on minor-free graphs of diameter prameterized by $D$, which were
known to be stochastically embeddable into bounded treewidth graphs with
expected additive distortion $\epsilon D$. We devise Ramsey-type embedding and
clan embedding analogs of the stochastic embedding. We use these embeddings to
construct the first (bicriteria quasi-polynomial time) approximation scheme
for the metric $\rho$-dominating set and metric $\rho$-independent set
problems in minor-free graphs.

###### Contents

  1. 1 Introduction
    1. 1.1 Applications
    2. 1.2 Paper Overview
    3. 1.3 Related Work
  2. 2 Preliminaries
    1. 2.1 Metric Embeddings
    2. 2.2 Minor Structure Theorem
  3. 3 Clan embedding into an ultrametric (Theorem 1)
    1. 3.1 Constructive Proof of Theorem 1
  4. 4 Clan Embedding into a Spanning Tree (Theorem 3)
    1. 4.1 Petal Decomposition Framework
    2. 4.2 Choosing a Radius
    3. 4.3 Proof of Lemma 5: the distributional case
    4. 4.4 Missing proofs from the create-petal procedure (Algorithm 3)
    5. 4.5 Grand finale: proof of Theorem 3
  5. 5 Lower Bound for Clan Embeddings into Trees (Theorem 2)
  6. 6 Ramsey Type Embedding for Minor-Free Graphs (Theorem 4)
  7. 7 Clan Embedding for Minor-Free Graphs (Theorem 5)
  8. 8 Applications
    1. 8.1 Metric $\rho$-Independent Set (Theorem 7)
    2. 8.2 Metric $\rho$-Dominating Set (Theorem 8)
    3. 8.3 Compact Routing Scheme (Theorem 6)
  9. A Path Distortion of Clan embeddings into ultrametrics
  10. B Local Search Algorithms
    1. B.1 Local search for $\rho$-dominating set under uniform measure
    2. B.2 Local search for $\rho$-independent set under uniform measure

##  1 Introduction

Low distortion metric embeddings provide a powerful algorithmic toolkit, with
applications ranging from approximation/sublinear/online/distributed
algorithms [LLR95, AMS99, BCL+18, KKM+12] to machine learning [GKK17], biology
[HBK+03], and vision [AS03]. Classically, we say that an embedding $f$ from a
metric space $(X,d_{X})$ to a metric space $(Y,d_{Y})$ has multiplicative
distortion $t$, if for every pair of points $u,v\in X$ it holds that
$d_{X}(u,v)\leq d_{Y}(f(u),f(v))\leq t\cdot d_{X}(u,v)$. Typical applications
of metric embeddings naturally have the following structures: take some
instance of a problem in a “hard” metric space $(X,d_{X})$; embed $X$ into a
“simple” metric space $(Y,d_{Y})$ via a low-distortion metric embedding $f$;
solve the problem in $Y$, and “pull-back” the solution in $X$. Thus, the
objectives are low distortion and “simple” target space.

Simple target spaces that immediately come to mind are Euclidean space and
tree metric, or — even better — an ultrametric. 111Ultrametric is a metric
space satisfying a strong form of the triangle inequality:
$d(x,z)\leq\max\left\\{d(x,y),d(y,z)\right\\}$ (for all $x,y,z$). Ultrametrics
embed isometrically into both Euclidean space [Lem03], and tree metric. See
Definition 1. In a celebrated result, Bourgain [Bou85] showed that every
$n$-point metric space embeds into Euclidean space with multiplicative
distortion $O(\log n)$ (which is tight [LLR95]). On the other hand, any
embedding of the $n$-vertex cycle graph $C_{n}$ into a tree metric will incur
multiplicative distortion $\Omega(n)$ [RR98]. Karp [Kar89] observed that
deleting a random edge from $C_{n}$ results in an embedding into a line with
expected distortion $2$ (see Figure 1(a)). This idea was developed by Bartal
[Bar96, Bar98] (improving over [AKPW95]), and culminating in the celebrated
work of Fakcharoenphol, Rao, and Talwar [FRT04] (see also [Bar04]) who showed
that every $n$-point metric space stochastically embeds into trees (actually
ultrametrics) with expected multiplicative distortion $O(\log n)$.
Specifically, there is a distribution $\mathcal{D}$, over dominating metric
embeddings 222Metric embedding $f:X\rightarrow Y$ is dominating if $\forall
u,v\in X$, $d_{X}(u,v)\leq d_{Y}(f(u),f(v))$. into trees (ultrametrics), such
that $\forall u,v\in X$,
$\mathbb{E}_{(f,T)\sim\mathcal{D}}d_{T}(f(u),f(v))\leq O(\log n)\cdot
d_{X}(u,v)$. The $O(\log n)$ multiplicative distortion is known to be optimal
[Bar96]. Stochastic embeddings into trees are widely successful and have found
numerous applications (see e.g. [Ind01]).

In many applications of metric embeddings, a worst-case distortion guarantee
is required. A different type of compromise (compared to expected distortion)
is provided by _Ramsey-type_ embeddings. The classical Ramsey problem for
metric spaces was introduced by Bourgain et al. [BFM86], and is concerned with
finding ”nice” structures in arbitrary metric spaces. Following [BBM06,
BLMN05a], Mendel and Naor [MN07] showed that for every integer parameter
$k\geq 1$, every $n$-point metric $(X,d)$ has a subset $M\subseteq X$ of size
at least $n^{1-1/k}$ that embeds into a tree (ultrametric) with multiplicative
distortion $O(k)$ (see [NT12, BGS16, ACE+20] for improvements). In fact, the
embedding has multiplicative distortion $O(k)$ for any pair in $M\times X$. We
say that the vertices in $M$ are _satisfied_ (see Figure 1(b) for an
illustration). As a corollary, every $n$-point metric space $(X,d_{X})$ admits
a collection ${\cal T}$ of $k\cdot n^{1/k}$ dominating trees over $X$ and a
mapping $\mbox{\bf home}:X\to{\cal T}$, such that for every $x,y\in X$, it
holds that $d_{\mbox{\bf home}(x)}(x,y)\leq O(k)\cdot d_{X}(x,y)$. These are
called Ramsey trees, and they have found applications to online algorithms
[BBM06], approximate distance oracles [MN07, Che15], and routing [ACE+20].

Figure 1: Three different types of embeddings of the cycle graph $C_{n}$ into
a tree. (a) On the left illustrated a stochastic embedding that is created by
deleting an edge $\\{v_{i},v_{i+1}\\}$ uniformly at random. The expected
multiplicative distortion of a pair of neighboring vertices $v_{j},v_{j+1}$ is
$\mathbb{E}[d_{T}(v_{j},v_{j+1})]=\frac{n-1}{n}\cdot
1+\frac{1}{n}\cdot(n-1)=\frac{2n-2}{n}<2$. By the triangle inequality and
linearity of expectation, the expected multiplicative distortion is $\leq 2$.
(b) In the middle illustrated a Ramsey type embedding: an arbitrary edge
$\\{v_{i},v_{i+1}\\}$ is deleted. The vertices in the subset $M$ (on the thick
red line), which constitutes a $(1-2\epsilon)$ fraction of the vertex set, are
satisfied. That is, they suffer from a multiplicative distortion at most
$\frac{1}{\epsilon}$ w.r.t. any other vertex.
(c) On the right illustrated a clan embedding, where $i$ is chosen uniformly
at random. The chief of a vertex $v_{j}$ denoted $\tilde{v}_{j}$. Each vertex
$v_{j}\in\\{v_{i+1-\epsilon n},\dots,v_{i+\epsilon n}\\}$ has additional copy
$v^{\prime}_{j}$; thus the probability that a vertex has two copies is
$2\epsilon$, implying that $\mathbb{E}[|f(v_{a})|]=1+2\epsilon$. The
distortion is
$\min\\{d(\tilde{v}_{a},\tilde{v}_{b}),d(v^{\prime}_{a},\tilde{v}_{b})\\}\leq\frac{1}{\epsilon}\cdot
d_{C_{n}}(v{}_{a},v_{b})$.

##### A new type of embedding: clan embedding

Recall that our initial goal was to embed a general metric space into a
“simple” target space, specifically a tree metric. A drawback of both the
stochastic embedding and the Ramsey-type embedding is that the embeddings are
actually into a collection of trees rather than into a single one; thus the
target space is not as simple as one might desire. Each embedding type makes a
different type of compromise: the distortion guaranteed in stochastic
embedding is only in expectation, while in the Ramsey-type embedding, only a
subset of the vertices enjoys a bounded distortion guarantee. In this paper,
we propose a novel type of compromise, which we call _clan embedding_. Here we
will have a single embedding with a worst-case guarantee on all vertex pairs.
The caveat is that each vertex might be mapped to multiple copies. This
violates the classical paradigm of having a one-to-one relationship between
the source and target spaces. However, we obtain a map into a single tree with
a worst-case guarantee; this is beneficial and opens a new array of
possibilities.

A _one-to-many_ embedding $f:X\rightarrow 2^{Y}$ maps each point $x$ into a
subset $f(x)\subseteq Y$ called the _clan_ of $x$. Each vertex $x^{\prime}\in
f(x)$ is called a _copy_ of $x$ (see Definition 2). Clan embedding is a pair
$(f,\chi)$, where $f$ is a one-to-many embedding, and $\chi:X\rightarrow Y$
maps each vertex $x$ to a special vertex $\chi(x)\in f(x)$ called the _chief_.
Clan embeddings are _dominating_ , that is, for every $x,y\in X$, the distance
between every two copies is at least the original distance:
$\min_{x^{\prime}\in f(x),y^{\prime}\in f(y)}d_{Y}(x^{\prime},y^{\prime})\geq
d_{X}(x,y)$. $(f,\chi)$ has multiplicative distortion $t$, if for every
$x,y\in X$, some vertex in the clan of $x$ is close to the chief of $y$:
$\min_{x^{\prime}\in f(x)}d_{Y}(x^{\prime},\chi(y))\leq t\cdot d_{X}(x,y)$
(see Definition 3). See Figure 1(c) for an illustration.

##### Clan embeddings into trees

One can easily construct an isometric clan embedding into a tree by allowing
$n$ copies for each vertex. On the other hand, with a single copy per vertex,
the clan embedding becomes a classic embedding, which requires a
multiplicative distortion of $\Omega(n)$. Our goal is to construct a low
distortion clan embedding, while keeping the number of copies each vertex has
as small as possible. To this end, we construct a distribution over clan
embeddings, where all the embeddings in the support have a worst-case
distortion guarantee; however, the expected number of copies each vertex has
is bounded by a constant arbitrarily close to $1$.

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

Given an $n$-point metric space $(X,d_{X})$ 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})$ 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 $16k$ such that for every
point $x\in X$, $\mathbb{E}_{f\sim\mathcal{D}}[|f(x)|]=O(n^{\frac{1}{k}})$.

We fist show that there exists a distribution $\mathcal{D}$ of clan embeddings
that has distortion and expected clan size via the minimax theorem. We then
use the multiplicative weights update (MWU) method to explicitly construct a
uniform distribution $\mathcal{D}$ of polynomial support as specified by
Theorem 1.

Our clan embedding into ultrametric is asymptotically tight (up to a constant
factor in the distortion), and cannot be improved even if we embed into a
general tree (rather than to the much more restricted structure of an
ultrametric). Additionally, our lower bound implies that the ultra-sparse
spanner construction of Elkin and Neiman [EN19] is asymptotically tight.
(Elkin and Neiman [EN19] constructed a spanner with stretch $O(\frac{\log
n}{\epsilon})$ and $(1+\epsilon)n$ edges; see Remark 2 for further details.)

######  Theorem 2 (Lower bound for clan embedding into a tree).

For every fixed $\epsilon\in(0,1)$ and large enough $n$, there is an $n$-point
metric space $(X,d_{X})$ such that for every clan embedding $(f,\chi)$ of $X$
into a tree with multiplicative distortion $O(\frac{\log n}{\epsilon})$, it
holds that $\sum_{x\in X}|f(x)|\geq(1+\epsilon)n$.
Furthermore, for every $k\in\mathbb{N}$, there is an $n$-point metric space
$(X,d_{X})$ such that for every clan embedding $(f,\chi)$ of $X$ into a tree
with multiplicative distortion $O(k)$, it holds that $\sum_{x\in
X}|f(x)|\geq\Omega(n^{1+\frac{1}{k}})$.

Often, we are given a weighted graph $G=(V,E,w)$, and the goal is to embed the
shortest path metric of the graph $d_{G}$ into a tree $T$. However, if, for
example, one is required to construct a network while using only pre-existing
edges from $E$, it is desirable that the tree $T$ will be a subgraph of $G$,
called a spanning tree. Abraham and Neiman [AN19] (improving over [EEST08])
constructed a stochastic embedding of general graphs into spanning trees with
expected distortion $O(\log n\log\log n)$ (losing a $\log\log n$ factor
compared to general trees [FRT04]). Later, Abraham et al. [ACE+20] constructed
Ramsey spanning trees, showing that for every $k\in\mathbb{N}$, every graph
can be embedded into a spanning tree with a subset $M$ of at least
$n^{1-\frac{1}{k}}$ satisfied vertices which suffers a distortion at most
$O(k\log\log n)$ w.r.t. any other vertex (again losing a $\log\log n$ factor
compared to general trees). Here we provide a “spanning” analog of Theorem 1.
Similar to [AN19, ACE+20], we also lose a $\log\log n$ factor compared to
general trees (see the introduction to Section 4 for further discussion). In
particular, by Theorem 2, our spanning clan embedding is optimal up to second-
order terms. As an application, we construct the first compact routing scheme
with routing tables of constant size in expectation; see Section 1.1.1. We say
that a clan embedding $(f,\chi)$ of a graph $G$ into a graph $H$ is _spanning_
if $f(V(G))=V(H)$ (i.e., every vertex in $H$ is an image of a vertex in $G$)
and for every edge $\\{v^{\prime},u^{\prime}\\}\in E(H)$ where $v^{\prime}\in
f(v),u^{\prime}\in f(u)$, it holds that $\\{v,u\\}\in E(G)$ (see Definitions 2
and 3).

######  Theorem 3 (Spanning clan embedding into trees).

Given an $n$-vertex weighted graph $G=(V,E,w)$ and parameter
$\epsilon\in(0,1]$, there is a distribution $\mathcal{D}$ over spanning clan
embeddings $(f,\chi)$ into trees with multiplicative distortion $O(\frac{\log
n\log\log n}{\epsilon})$ such that for every vertex $v\in V$,
$\mathbb{E}_{f\sim\mathcal{D}}[|f(v)|]\leq 1+\epsilon$.

In addition, for every $k\in\mathbb{N}$, there is a distribution $\mathcal{D}$
over spanning clan embeddings $(f,\chi)$ into trees with multiplicative
distortion $O(k\log\log n)$, where for every vertex $v\in V$,
$\mathbb{E}_{f\sim\mathcal{D}}[|f(v)|]=O(n^{\frac{1}{k}})$.

##### Clan embedding of minor-free graphs into bounded treewidth graphs

As [Bou85] and [FRT04] are tight, a natural question arises: by embedding from
a simpler space (than general $n$-point metric space) into a richer space
(than trees), could the distortion be reduced? The family of low-treewidth
graphs is an excellent candidate for a target space: it is a much more
expressive target space than trees, while many hard problems remain tractable.
Unfortunately, by the work of Chakrabarti et al. [CJLV08] (see also [CG04]),
there are $n$-vertex planar graphs such that every (stochastic) embedding into
$o(\sqrt{n})$-treewidth graphs must incur expected multiplicative distortion
$\Omega(\log n)$. Bypassing this roadblock, Fox-Epstein et al. [FKS19]
(improving over [EKM14]), showed how to embed planar metrics into bounded
treewidth graphs while incurring only a small _additive_ distortion.
Specifically, given a planar graph $G$ and a parameter $\epsilon$, they
constructed a deterministic dominating embedding $f$ into a graph $H$ of
treewidth $\mathrm{poly}(\frac{1}{\epsilon})$, such that $\forall u,v\in G$,
$d_{H}(f(u),f(v))\leq d_{G}(u,v)+\epsilon D$, where $D$ is the diameter of
$G$. While $\epsilon D$ looks like a crude additive bound, it suffices to
obtain approximation schemes for several classic problems: $k$-center, vehicle
routing, metric $\rho$-dominating set, and metric $\rho$-independent set.

Following the success in planar graphs, Cohen-Addad et al. [CFKL20] wanted to
generalize to minor-free graphs. Unfortunately, they showed that already
obtaining additive distortion $\frac{1}{20}D$ for $K_{6}$-minor-free graphs
requires the host graph to have treewidth $\Omega(\sqrt{n})$. Inspired by the
case of trees, [CFKL20] bypass this barrier by constructing a stochastic
embedding from $K_{r}$-minor-free $n$-vertex graphs into a distribution over
treewidth-$O_{r}(\frac{\log n}{\epsilon^{2}})$ graphs with expected additive
distortion $\epsilon D$, 333$O_{r}$ hides some function depending only on $r$.
That is, there is some function $\chi:\mathbb{N}\rightarrow\mathbb{N}$ such
that $O_{r}(x)\leq\chi(r)\cdot x$. that is $\forall u,v\in G$,
$\mathbb{E}_{(f,H)\sim\mathcal{D}}[d_{H}(f(u),f(v))]\leq d_{G}(u,v)+\epsilon
D$. Similar to the case in planar graphs, Cohen-Addad et al. [CFKL20] used
their embedding to construct an approximation scheme for the capacitated
vehicle routing problem in $K_{r}$-minor-free graphs. However, due to the
stochastic nature of the embedding, it was not strong enough to imply any
results for the metric $\rho$-dominating/independent problems in minor-free
graphs, which, prior to our work, remain wide open.

In this paper, similar to the case of trees, we construct Ramsey-type and clan
embedding analogs to the stochastic embedding of [CFKL20]. Our Ramsey-type
embedding bypasses the lower bound of $\Omega(\sqrt{n})$ from [CFKL20] while
guaranteeing a worst-case distortion (for a large random subset of vertices).
As an application, we obtain a bicriteria quasi-polynomial time approximation
scheme (QPTAS) ${}^{\ref{foot:approximationSchemes}}$ for the metric
$\rho$-independent set problem in minor-free graphs (see Section 1.1.2).

######  Theorem 4 (Ramsey-type embedding for minor-free graphs).

Given an $n$-vertex $K_{r}$-minor-free graph $G=(V,E,w)$ with diameter $D$ and
parameters ${\epsilon\in(0,\frac{1}{4})}$, $\delta\in(0,1)$, there is a
distribution over dominating embeddings $g:G\rightarrow H$ into graphs of
treewidth $O_{r}(\frac{\log^{2}n}{\epsilon\delta})$, such that there is a
subset $M\subseteq V$ of vertices for which the following claims hold:

  1. 1.

For every $u\in V$, $\Pr[u\in M]\geq 1-\delta$.

  2. 2.

For every $u\in M$ and $v\in V$, $d_{H}(g(u),g(v))\leq d_{G}(u,v)+\epsilon D$.

By setting $\delta=\frac{1}{2}$ and repeating $\log n$ times, a
straightforward corollary is the following.

######  Corollary 1.

Given a $K_{r}$-minor-free $n$-vertex graph $G=(V,E,w)$ with diameter $D$ and
parameter $\epsilon\in(0,\frac{1}{4})$, there are $\log n$ dominating
embeddings $g_{1},\dots,g_{\log n}$ into graphs of treewidth
$O_{r}(\frac{\log^{2}n}{\epsilon})$, such that for every vertex $v$, there is
some embedding $g_{i_{v}}$, such that

$\forall u\in V,\qquad d_{H_{i_{v}}}(g_{i_{v}}(u),g_{i_{v}}(v))\leq
d_{G}(u,v)+\epsilon D\leavevmode\nobreak\ .$

While Ramsey-type embedding is sufficient for the metric $\rho$-independent
set problem (as we can restrict our search to independent sets in $M$), we
cannot use it for the metric $\rho$-dominating set problem (as every good
solution might contain vertices outside $M$). To resolve this issue, we
construct a clan embedding of minor-free graphs into bounded treewidth graphs.
As we have a worst-case distortion guarantee for all vertex pairs, we obtain a
QPTAS ${}^{\ref{foot:approximationSchemes}}$ for the metric $\rho$-dominating
set problem in minor-free graphs (see Section 1.1.2).

######  Theorem 5 (Clan embedding for minor-free graphs).

Given a $K_{r}$-minor-free $n$-vertex graph $G=(V,E,w)$ of diameter $D$ and
parameters $\epsilon\in(0,\frac{1}{4})$, $\delta\in(0,1)$, there is a
distribution $\mathcal{D}$ over clan embeddings $(f,\chi)$ with additive
distortion $\epsilon D$ into graphs of treewidth
$O_{r}(\frac{\log^{2}n}{\delta\epsilon})$ such that for every $v\in V$,
$\mathbb{E}[|f(v)|]\leq 1+\delta$.

###  1.1 Applications

####  1.1.1 Compact Routing Scheme

A _routing scheme_ in a network is a mechanism that allows packets to be
delivered from any node to any other node. The network is represented as a
weighted undirected graph, and each node can forward incoming data by using
local information stored at the node, called a _routing table_ , and the
(short) packet’s _header_. The routing scheme has two main phases: in the
preprocessing phase, each node is assigned a routing table and a short _label_
; in the routing phase, when a node receives a packet, it should make a local
decision, based on its own routing table and the packet’s header (which may
contain the label of the destination, or a part of it), of where to send the
packet. The stretch of a routing scheme is the worst-case ratio between the
length of a path on which a packet is routed to the shortest possible path.

Compact routing schemes were extensively studied [PU89, ABLP90, AP92, Cow01,
EGP03, TZ01, Che13, ACE+20], starting with Peleg and Upfal [PU89]. Using
$\tilde{O}(n^{\frac{1}{k}})$ table size, Awerbuch et al. [ABLP90] obtained
stretch $O(k^{2}9^{k})$, which was improved later to $O(k^{2})$ by Awerbuch
and Peleg [AP92]. In their celebrated compact routing scheme, Thorup and Zwick
[TZ01] obtained stretch $4k-5$ while using $O(k\cdot n^{1/k})$ size tables and
labels of size $O(k\log n)$. 444Unless stated otherwise, we measure space in
machine words, each word is $\Theta(\log n)$ bits. The stretch was improved to
roughly $3.68k$ by Chechik [Che13], using a scheme similar to [TZ01] (while
keeping all other parameters intact). Recently, Abraham et al. [ACE+20] devise
a compact routing scheme (using Ramsey spanning trees) with labels of size
$O(\log n)$, tables of size $O(k\cdot n^{1/k})$, and stretch $O(k\log\log n)$.

In all previous works, the guarantees on the table size are worst case. That
is, the table size of every node in the network is bounded by a certain
parameter. Here our guarantee is only in expectation. Note that such an
expected guarantee makes a lot of sense for a central planner constructing a
routing scheme for a network where the goal is to minimize the total amount of
resources rather than the maximal amount of resources in a single spot. Even
though previous works analyzed worst-case guarantees, if one tries to analyze
their expected bounds per vertex, the guarantees will not be improved. Our
contribution is the following:

[capbesideposition=left,top,capbesidewidth=8.1cm]table[]  Routing s. Stretch
Label Table 1. [TZ01] $4k-5$ $O(k\log n)$ $O(kn^{1/k})$ 2. [Che13] $3.68k$
$O(k\log n)$ $O(kn^{1/k})$ 3. [ACE+20] $O(k\log\log n)$ $O(\log n)$
$O(kn^{1/k})$ 4. Thm. 6 $O(k\log\log n)$ $O(\log n)$ $O(n^{1/k})^{(*)}$ 5.
[TZ01] $O(\log n)$ $O(\log^{2}n)$ $O(\log n)$ 6. [Che13] $O(\log n)$
$O(\log^{2}n)$ $O(\log n)$ 7. [ACE+20] $O(\log n)$ $O(\log n)$ $O(\log^{2}n)$
8. [ACE+20] $\widetilde{O}(\log n)$ $O(\log n)$ $O(\log n)$ 9. Thm. 6 $O(\log
n)$ $O(\log n)$ $O(\log n)^{(*)}$ 10. Thm. 6 $\widetilde{O}(\log n)$ $O(\log
n)$ $\boldsymbol{O(1)}^{(*)}$

Table 1: The table compares various routing schemes for $n$-vertex graphs. In
rows 1-4, we compare different schemes in their full generality, here $k$ is
an integer parameter. In rows 5,6,8,10, we fix $k=\log n$, while in rows 7 and
9, we fix $k=\frac{\log n}{\log\log n}$. Note that our result in line 9 is
superior to all previous results: it has reduced label size compared to lines
5-6, reduced table size compared to line 7, and reduced stretch compared to
line 8. Our result in line 10 is the first to obtain a constant table size.
The sizes of the table and label are measured in words, each word is $O(\log
n)$ bits. The header size is asymptotically equal to the label size in all the
compared routing schemes. The main caveat is that, while in all previous
results the table size is analyzed w.r.t. a worst-case guarantee, we only
provide bounds in expectation (marked by (*)). The label size (as well as the
stretch) is a worst-case guarantee in our work as well.

######  Theorem 6 (Compact routing scheme).

Given a weighted graph $G=(V,E,w)$ on $n$ vertices and integer parameter
$k>1$, there is a compact routing scheme with stretch $O(k\log\log n)$ that
has (worst-case) labels (and headers) of size $O(\log n)$, and the expected
size of the routing table of each vertex is $O(n^{1/k})$.

See Table 1 for comparison of our and previous results. We mainly focus on the
very compact regime where all the parameters are at most poly-logarithmic. A
key result in [TZ01] is a stretch $1$ routing scheme for the special case of a
tree, where a routing table has constant size, and logarithmic label size (see
Theorem 13). All the previous works are based on constructing a collection of
trees. Specifically, in [TZ01, Che13], there are $n$ trees, where each vertex
belongs to $O(\log n)$ trees, and for each pair of nodes, there is a tree that
guarantees a small stretch. Routing is then done in that tree. This is the
reason for their large label size of $\log^{2}n$ (as a label consists of $\log
n$ labels in different trees). [ACE+20] constructs $\log n$ (Ramsey spanning)
trees in total, where each vertex $v$ has a home tree $T_{v}$, such that $v$
enjoys a small stretch w.r.t. any other vertex in $T_{v}$. The label then
consists of the name of $T_{v}$ and the label of $v$ in $T_{v}$. However, the
routing table is still somewhat large as one needs to store the routing
information in $\log n$ different trees.

In contrast, our construction is based on the spanning clan embedding
$(f,\chi)$ of Theorem 3 into a single tree $T$, where the clan of each vertex
consists of $O(1)$ copies (in expectation). The label of each vertex $v$ is
simply the label of $\chi(v)$ in $T$. The routing table of $v$ contains the
routing tables of all the corresponding copies in $f(v)$.

####  1.1.2 Metric Baker Problems in Minor-free graphs

Baker [Bak94] introduced a “layering” technique in order to construct
efficient polynomial approximation schemes (EPTAS) 555A polynomial time
approximation scheme (PTAS) is an algorithm that for any fixed
$\epsilon\in(0,1)$, provides a $(1+\epsilon)$-approximation in polynomial
time. A PTAS is an _efficient_ polynomial time approximation scheme (EPTAS) if
running time is of the form $n^{O(1)}\cdot f(\epsilon)$ for some function
$f(.)$ depending on $\epsilon$ only. A quasi-polynomial time approximation
scheme (QPTAS) has running time $2^{\cdot\mathrm{polylog}(n)}$ for every fixed
$\epsilon$. for many “local” problems in planar graphs such as minimum-measure
_dominating set_ and maximum-measure _independent set_. The key observation is
that planar graphs have the “bounded local treewidth” property. Baker showed
that for some problems solvable on bounded treewidth graphs, one can construct
efficient approximation schemes for graphs possessing the bounded local
treewidth property. This approach was generalized by Demaine et al. [DHK05] to
minor-free graphs.

Eisenstat et al. [EKM14] proposed metric generalizations of Baker problems:
minimum measure $\rho$_-dominating set_ , and maximum measure
$\rho$_-independent set_. Given a metric space $(X,d_{X})$, a
$\rho$-independent set is a subset $S\subseteq X$ of points such that for
every $x,y\in S$, $d_{X}(x,y)>\rho$. Similarly, a $\rho$-dominating set is a
subset $S\subseteq X$ such that for every $x\in X$, there exists $y\in S$,
such that $d_{X}(x,y)\leq\rho$. Given a measure
$\mu:X\rightarrow\mathbb{R}_{+}$, the goal of the metric $\rho$-dominating
(resp. independent) set problem is to find a $\rho$-dominating (resp.
independent) set of minimum (resp. maximum) measure. It is often the case that
metric Baker problems are much easier under the uniform measure. Sometimes, in
addition, we are given a set of terminals ${\cal K}\subseteq X$, and required
only that the terminals will be dominated ($\forall x\in{\cal
K},\leavevmode\nobreak\ \exists y\in S$ s.t. $d_{X}(x,y)\geq\rho$). Note that
the metric generalization of Becker problems in structured graphs (e.g.
planar) is considerably harder than the non-metric problems. This is because
the graph describing dominance/independence relations no longer posses the
original structure (e.g. planarity).

An approximation scheme for the $\rho$-dominating (resp. independent) set
problem returns a $\rho$-dominating (resp. independent) set $S$ such that for
every $\rho$-dominating (resp. independent) set $S^{\prime}$ it holds that
$\mu(S)\leq(1+\epsilon)\mu(S^{\prime})$ (resp.
$\mu(S)\geq(1-\epsilon)\mu(S^{\prime})$). A bicriteria approximation scheme
for the $\rho$-dominating (resp. independent) set problem returns a
$(1+\epsilon)\rho$-dominating (resp. $(1-\epsilon)\rho$-independent) set $S$
such that for every $\rho$-dominating (resp. independent) set $S^{\prime}$ it
holds that $\mu(S)\leq(1+\epsilon)\mu(S^{\prime})$ (resp.
$\mu(S)\geq(1-\epsilon)\mu(S^{\prime})$).

For unweighted graphs with treewidth $\mathrm{tw}$, Borradaile and Le [BL16]
provided an exact algorithm for the $\rho$-dominating set problem with
$O((2\rho+1)^{\mathrm{tw}+1}n)$ running time (see also [DFHT05]). For general
treewidth $\mathrm{tw}$ graphs, using dynamic programming technique,
Katsikarelis et al. [KLP19] designed a fixed parameter tractable (FPT)
approximation algorithm for the metric $\rho$-dominating set problem with
$(\mathrm{tw}/\epsilon)^{O(\mathrm{tw})}\cdot\mathrm{poly}(n)$ runtime that
returns a $(1+\epsilon)\rho$-dominating set $S$, such that for every
$\rho$-dominating set $S^{\prime}$ it holds that $\mu(S)\leq\mu(S^{\prime})$.
A similar result was also obtained for the metric $\rho$-independent set
problem [KLP20]. In particular, for the very basic case of bounded treewidth
graphs, no true approximation scheme (even with quasi-polynomial time) is
known for these problems. Additional evidence was provided by Marx and
Pilipczuk [MP15] (see also [FKS19]), who showed that the existence of EPTAS
${}^{\ref{foot:approximationSchemes}}$ for either
$\rho$-dominating/independent set problem in planar graphs would refute the
exponential-time hypothesis (ETH). Given this evidence, it is natural to
settle for bicriteria approximation.

For unweighted planar graphs and constant $\rho$, there are linear time
approximation schemes (not bicriteria) for the metric
$\rho$-independent/dominating set problems [EILM16, DFHT05]. In weighted
planar graphs, under the uniform measure, Marx and Pilipczuk [MP15] gave exact
$n^{O(\sqrt{k})}$ time solution to both metric $\rho$-dominating/isolated set
problems, provided that the solution is guaranteed to be of size at most $k$.
Using their embedding of planar graphs into $\epsilon^{-O(1)}\log n$-treewidth
graphs with additive distortion $\epsilon D$, Eisenstat et al. [EKM14]
provided a bicriteria PTAS ${}^{\ref{foot:approximationSchemes}}$ for both
metric $\rho$-independent/dominating set problems in planar graphs. Later, by
constructing an improved embedding into $\epsilon^{-O(1)}$-treewidth graphs,
Fox-Epstein et al. [FKS19] obtained a bicriteria
EPTAS.${}^{\ref{foot:approximationSchemes}}$

Reference | Family | Result | Technique
---|---|---|---
1. | [MP15] | planar | No EPTAS under ETH |
2. | [KLP19, KLP20] | treewidth | FPT with approx $(1+\epsilon)\rho$ | Dynamic programming
3. | [EKM14] | planar | Bicriteria PTAS | Deterministic embedding
4. | [FKS19] | planar | Bicriteria EPTAS | Deterministic embedding
5. | Theorems 17&18 | minor-free | PTAS (uniform measure) | Local search
6. | Theorems 7&8 | minor-free | Bicriteria QPTAS | Clan/Ramsey type embedding

Table 2: The table compares different approximation schemes for metric Becker
problems on weighted graphs. All compared results apply to both metric
$\rho$-dominating/independent set problems. All the results (other than in
line 5) apply to the general measure case.

Finally, we turn to the most challenging case of minor-free graphs. For the
restricted uniform measure case, using local search (similarly to [CKM19]), we
construct PTAS for both metric $\rho$-dominating/independent set problems. See
Theorems 17 and 18 in Appendix B for details. However, the local search
approach seems to be hopeless for general measures. Alternately, one can try
the metric embedding approach (for which bicriteria approximation is
unavoidable). Unfortunately, unlike the classic embeddings in [EKM14, FKS19],
Cohen-Addad et al. [CFKL20] provided a stochastic embedding with an _expected
distortion_ guarantee. Such a stochastic guarantee is not strong enough to
construct approximation schemes for the metric $\rho$-independent/dominating
set problems. Using our clan and Ramsey-type embeddings, we are able to
provide the first bicriteria QPTAS ${}^{\ref{foot:approximationSchemes}}$ for
these problems. See Table 2 for a summary of previous and current results.

######  Theorem 7 (Metric $\rho$-independent set).

There is a bicriteria quasi-polynomial time approximation scheme (QPTAS) for
the metric $\rho$-independent set problem in $K_{r}$-minor-free graphs.
Specifically, given a weighted $n$-vertex $K_{r}$-minor-free graph
$G=(V,E,w)$, measure $\mu:V\rightarrow\mathbb{R}_{+}$ and parameters
$\epsilon\in(0,\frac{1}{4})$, $\rho>0$, in
$2^{\tilde{O}_{r}(\frac{\log^{2}n}{\epsilon^{2}})}$ time, one can find a
$(1-\epsilon)\rho$-independent set $S\subseteq V$ such that for every
$\rho$-independent set $\tilde{S}$, $\mu(S)\geq(1-\epsilon)\mu(\tilde{S})$.

######  Theorem 8 (Metric $\rho$-dominating set).

There is a bicriteria quasi-polynomial time approximation scheme (QPTAS) for
the metric $\rho$-dominating set problem in $K_{r}$-minor-free graphs.
Specifically, given a weighted $n$-vertex $K_{r}$-minor-free graph
$G=(V,E,w)$, measure $\mu:V\rightarrow\mathbb{R}_{+}$, a subset of terminals
${\cal K}\subseteq V$, and parameters $\epsilon\in(0,\frac{1}{4})$, $\rho>0$,
in $2^{\tilde{O}_{r}(\frac{\log^{2}n}{\epsilon^{2}})}$ time, one can find a
$(1+\epsilon)\rho$-dominating set $S\subseteq V$ for ${\cal K}$ such that for
every $\rho$-dominating set $\tilde{S}$ of ${\cal K}$ ,
$\mu(S)\leq(1+\epsilon)\mu(\tilde{S})$.

###  1.2 Paper Overview

The paper overview uses terminology presented in the preliminaries Section 2.

##### Clan embedding into ultrametric

The main task is to prove a “distributional” version of Theorem 1.
Specifically, given a parameter $k$, and a measure
$\mu:X\rightarrow\mathbb{R}_{\geq 1}$, we construct a clan embedding with
distortion $16k$ such that $\sum_{x\in
X}\mu(x)\cdot|f(x)|\leq\mu(X)^{1+\frac{1}{k}}$, where $\mu(X)=\sum_{x\in
X}\mu(x)$ (Lemma 2). We show that the distributioal version implies Theorem 1
by using the minimax theorem.

The algorithm to construct the distributional version is a deterministic
recursive ball growing algorithm, which is somewhat similar to previous
deterministic algorithms constructing Ramsey trees [Bar11, ACE+20]. Let $D$ be
the diameter of the metric space. We grow a ball $B(v,R)$ around a point $v$
and partition the space into two clusters: the interior $B(v,R+\frac{D}{16k})$
and exterior $X\setminus B(v,R-\frac{D}{16k})$ of the ball, while points at
distance $\frac{D}{16k}$ from the boundary of the ball belong to both
clusters. We then recursively create a clan embedding into ultrametrics for
each of the two clusters. These two embeddings are later combined into a
single ultrametric where the root has label $D$. See Figure 2 for an
illustration. The $16k$ distortion guarantee follows from the wide “belt”
around the boundary of the ball belonging to both clusters. Note that the
images of vertices in this “belt” contain copies in the clan embeddings of
both clusters, while “non-belt” points have copies in a single embedding only.
However, the two clusters have cardinality smaller than $|X|$. The key is to
carve the partition while guaranteeing that the relative measure of points
belonging to both clusters will be small compared to the reduction in
cardinality.

##### Spanning clan embedding into trees

In Theorem 3, the spanning version, we try to imitate the approach of Theorem
1. However, we cannot simply carve balls and continue recursively. The reason
is that the diameter of a cluster could grow unboundedly after deleting some
vertices. In particular, there is no clear upper bound on the distance between
separated points.

To imitate the ball growing approach nonetheless, we use the petal-
decomposition framework that was previously applied to create stochastic
embedding into spanning trees [AN19], and Ramsey spanning trees [ACE+20]. The
petal decomposition framework enables one to iteratively construct a spanning
tree for a given graph. In each level, the current cluster is partitioned into
smaller diameter pieces (called _petals_), which have properties resembling
balls. The algorithm continues recursively on the petals. Later, the petals
are connected back to create a spanning tree. The key property is that while
creating a petal, we have a certain degree of freedom to chose its “radius”,
which enables us to use the ball growing approach from above. Crucially, the
framework guarantees that for every choice of radii (within the sepecified
limits), the diameter of the resulting tree will be only constant times larger
than that of the original graph. However, the petal decomposition framework
does not provide us with the freedom to choose the center of the petal. This
makes the task of controlling the number of copies more subtle.

##### Lower bound for clan embedding into a tree

We provide here a proof sketch for the first assertion in Theorem 2. We begin
by constructing an $n$-vertex graph $G=(V,E)$ with $(1+\epsilon)n$ edges and
girth $g=\Omega(\frac{\log n}{\epsilon})$; the girth is the length of the
shortest cycle. Consider an arbitrary clan embedding of $G$ into a tree $T$
with distortion $\frac{g}{c}=O(\frac{\log n}{\epsilon})$ (for some constant
$c$) and $\kappa$ copies overall. We create a new graph $H$ by merging all the
copies of each vertex into a single vertex. There is a naturally defined
classic embedding from $G$ to $H$ with distortion $\leq\frac{g}{c}$. The Euler
characteristic of the graph $G$ equals $\chi(G)=|E|-|V|+1=\epsilon n+1$, while
the Euler characteristic of $H$ is at most $\chi(H)\leq\kappa-n$. However,
Rabinovich and Raz [RR98] showed that, if an embedding from a girth-$g$ graph
$G$ has distortion $\leq\frac{g}{c}$, the host graph must have the Euler
characteristic at least as large as that of $G$. Thus, we conclude that
$\kappa\geq(1+\epsilon)n+1$ as required.

##### Ramsey type embedding for minor-free graphs

The structure theorem of Robertson and Seymour [RS03] stated that every minor-
free graph can be decomposed into a collection of graphs embedded on the
surface of constant genus (with some vortices and apices), glued together into
a tree structure by taking clique-sums. The stochastic embedding of minor free
graphs into a distribution over bounded treewidth graphs by Cohen-Addad et al.
[CFKL20] was constructed according to the layers of the structure theorem.
First, they constructed an embedding for a planar graph with a single vortex.
Then, they generalized it to planar graphs with multiple vortices,
subsequently to graphs embedded on the surface of constant genus with multiple
vortices, and to surface embeddable graphs with multiple vortices and apices.
Finally, they incorporated cliques-sums and generalized to minor-free graphs.
Most crucially, for this paper, the only step requiring randomness was the
incorporation of apices. Specifically, [CFKL20] constructed a deterministic
embedding for graphs embedded on the surface of constant genus with multiple
vortices. This is the starting point of our embeddings.

Our first step is to incorporate apices, however, instead of guaranteeing that
the distance of each pair is distorted by $\epsilon D$ in expectation, we will
show that each vertex with probability $1-\delta$ enjoys a small distortion
w.r.t. any other vertex. We begin by deleting all the apices $\Psi$ and
obtaining a surface embeddable graph with multiple vortices
$G^{\prime}=G[V\setminus\Psi]$. However, the diameter of the resulting graph
is essentially unbounded. Pick an arbitrary vertex $r$, and partition
$G^{\prime}$ into layers of width $O(\frac{D}{\delta})$ w.r.t. distances from
$r$ with a random shift 666Alternatively, one could use here a strong padded
decomposition [Fil19] (as in [CFKL20]) into clusters of diameter
$O_{r}(\frac{D}{\delta})$ such that each radius-$D$ ball is fully contained in
a single cluster with probability $1-\delta$. However, this approach will not
work for our clan embedding, as there is no bound on the number of copies we
will need for failed vertices. We use the layering approach for the Theorem 4
as well to keep the proofs of Theorems 4 and 5 similar.. It follows that every
vertex $v$ is $2D$-padded (that is, the ball $B(v,2D)$ is fully contained in a
single layer) with probability $1-\delta$. The set $M$ of _satisfied_ vertices
defined to be the set of all $D$-padded vertices. We then use the
deterministic embedding from [CFKL20] on every layer with distortion parameter
$\epsilon^{\prime}=\Theta(\epsilon\delta)$ to incur additive distortion
$\epsilon D$. Finally, we combine all these embeddings together into a single
embedding, which also contains the apices.

The next step is to incorporate clique-sums. This is done recursively w.r.t.
the clique-sum decomposition tree $\mathbb{T}$. In each step, we pick a
central piece $\tilde{G}\in\mathbb{T}$ such that
$\mathbb{T}\setminus\tilde{G}$ breaks into connected components
$\mathbb{T}_{1},\mathbb{T}_{2},\dots$, where each $\mathbb{T}_{i}$ contains at
most $|\mathbb{T}|/2$ pieces. We construct a Ramsey-type embedding for
$\tilde{G}$ using the lemma above and obtain a set $\tilde{M}$ of satisfied
vertices. Recursively, we construct a Ramsey-type embedding for each
$\mathbb{T}_{i}$ and obtain a set $M_{i}$ of satisfied vertices. We ensure
that all these embeddings are clique-preserving. Thus even though eventually
we will obtain a one-to-one embedding, during the process, we keep them _one-
to-many and clique-preserving_. This provides us with a natural way to combine
all the embeddings of $\tilde{G},\mathbb{T}_{1},\mathbb{T}_{2},\dots$ into a
single embedding into a graph of bounded treewidth (by identifying vertices of
respective clique copies). All the vertices in $\tilde{M}$ will be satisfied.
A vertex $v\in\mathbb{T}_{i}$ will be satisfied if $v\in M_{i}$ and all the
vertices in the clique $Q_{i}$, used in the clique sum of $\tilde{G}$ with
$\mathbb{T}_{i}$, are satisfied $Q_{i}\subseteq\tilde{M}$. Analyzing the
entire process, we show that each vertex is satisfied with probability at
least $(1-\delta)^{\log n}$. The theorem follows by setting the parameter
$\delta^{\prime}=\Theta(\frac{\delta}{\log n})$.

##### Clan embedding for minor-free graphs

The construction here follows similar lines to our Ramsey-type embedding.
However, we cannot simply “give-up” on vertices, as we required to provide a
worst-case distortion guarantee on all vertex pairs. Similarly to the Ramsey-
type case, we build on the deterministic embedding of surface embeddable
graphs with vortices from [CFKL20], and generalize it to a clan embedding of
graphs including the apices. However, there is one crucial difference in
creating the “layering” (with the random shift). In the Ramsey-type embedding,
vertices near the boundary between two layers simply failed and did not join
$M$. Here, instead, the layers will somewhat overlap such that copies of
vertices near boundary areas will be split into two unrelated sets. In
particular, cliques that lie near boundary areas will have two separated
clique copies w.r.t. each corresponding layer (at most two). Even though that
actually each vertex will have an essentially unbounded number of copies (due
to the clique-preservation requirement), the copies of each vertex will be
divided to either one or two sets, such that in the final embedding, it will
be enough to pick an arbitrary single copy from each set. The copies of a
vertex will split into two sets only if it is in the area of the boundary, the
probability of which is bounded by $\delta$.

The generalization to clique-sums also follows similar lines to the Ramsey-
type embedding. We create a clan embedding for $\tilde{G}$ into treewidth
graph $\tilde{H}$ as above, and recursively clan embeddings
$H_{1},H_{2},\dots$ for $\mathbb{T}_{1},\mathbb{T}_{2},\dots$. For each
$\mathbb{T}_{i}$, we will make the vertices of the clique $Q_{i}$, used for
the clique-sum between $\tilde{G}$ and $\mathbb{T}_{i}$, into apices, thereby
ensuring that $H_{i}$ will succeed on $Q_{i}$. In particular, every vertex
$v\in Q_{i}$ will have a single copy in $H_{i}$. When combining $H_{i}$ with
$\tilde{H}$, there are two cases. If the embedding $\tilde{H}$ was successful
w.r.t. $Q_{i}$ we will simply identify between the two clique copies and done.
Otherwise, $\tilde{H}$ will contain two vertex-disjoint clique copies
$\tilde{Q}_{i}^{1},\tilde{Q}_{i}^{2}$ of $Q_{i}$. We will create two disjoint
copies of the embedding $H_{i}$: $H_{i}^{1},H_{i}^{2}$, and identify the two
copies of $Q_{i}$ in $H_{i}^{1},H_{i}^{2}$ with
$\tilde{Q}_{i}^{1},\tilde{Q}_{i}^{2}$, respectively. It follows that for a
vertex $v\in\mathbb{T}_{i}$, with probability at least $1-\delta$, the number
of copies it will have is the same as in $H_{i}$, while with probability at
most $\delta$ it will be doubled. Analyzing the entire process (and picking a
single copy from each relevant set as above), we show that each vertex is
expected to have at most $(1+\delta)^{\log n}$ copies. The theorem follows by
using the parameter $\delta^{\prime}=\Theta(\frac{\delta}{\log n})$.

###  1.3 Related Work

Path-distortion A closely related notion to clan embeddings is multi-embedding
studied by Bartal and Mendel [BM04]. A multi-embedding is a dominating one-to-
many embedding. The distortion guarantee, however, is very different. We say
that a multi-embedding $f:X\rightarrow 2^{Y}$ between metric spaces
$(X,d_{X})$, $(Y,d_{Y})$ has _path distortion_ $t$, if for every “path” in
$X$, i.e., a sequence of points $x_{0},x_{1},\dots,x_{q}$, there are copies
$x^{\prime}_{i}\in f(x_{i})$ such that
$\sum_{i=0}^{q-1}d_{Y}(x^{\prime}_{i},x^{\prime}_{i+1})\leq
t\cdot\sum_{i=0}^{q-1}d_{X}(x_{i},x_{i+1})$. For $n$ point metric space
$(X,d)$ with aspect ratio $\Phi$ 777The aspect ratio of a metric space $(X,d)$
is the ratio between the maximal and minimal distances
$\frac{\max_{x,y}d(x,y)}{\min_{x\not=y}d(x,y)}$., and parameter $k\geq 1$,
Bartal and Mendel [BM04] constructed a multi-embedding into ultrametric with
$O(n^{1+\frac{1}{k}})$ vertices and distortion $O(k\cdot\min\\{\log
n\cdot\log\log n,\log\Phi\cdot\log\log\Phi\\})$. Formally, path distortion and
multiplicative distortion of clan embedding are incomparable, as clan
embedding guarantees small distortion with respect to a single chief vertex
(which is crucial to our applications), while the multi-embedding [BM04]
distortion guarantee is w.r.t. arbitrary copies, but preserve entire “paths”.
Interestingly, a small modification to our clan embedding provides the path
distortion guarantee as well! See Theorem 15 in Appendix A. Specifically, we
obtain embedding into ultrametric with $O(n^{1+\frac{1}{k}})$ (resp.
$(1+\epsilon)n$) vertices and distortion $O(k\cdot\min\\{\log n,\log\Phi\\})$
(resp. $O(\frac{\log n}{\epsilon}\cdot\min\\{\log n,\log\Phi\\})$), shaving a
$\log\log$ factor compared with [BM04]. In a private communication, Bartal
told us that he obtained the exact same path distortion guarantees more than a
decade ago; Bartal’s manuscript is made public recently [Bar21].

In a concurrent paper, Haeupler et al. [HHZ21] studied a closely related
notion of tree embeddings with copies. They construct a one-to-many embedding
of a graph $G$ into a tree $T$ where every vertex has at most $O(\log n)$
copies, and such that every connect subgraph $H$ of $G$ has a connected copy
$H^{\prime}$ in $T$, of weight at most $O(\log^{2}n)\cdot w(H)$. Using the
path distortion gurantee in our embedding (or [Bar21]), one will obtain an
embedding such that every connect subgraph $H$ of $G$ has a connected copy
$H^{\prime}$ in $T$, of weight at most $O(\log n)\cdot w(H)$, however the
bound on the maximal number of copies will be only polynomial.

Tree covers. The constructions of Ramsey trees are asymptotically tight
[BBM06]. Furthermore, as was shown by Bartal et al. [BFN19] that they cannot
be substantially improved even for planar graphs with a constant doubling
dimension. 888Specifically, for every $\alpha>0$, [BFN19] constructed planar
graph with constant doubling dimension, such that for every tree embedding,
the subset of vertices enjoying distortion $\leq\alpha$ is of size at most
$n^{1-\Omega(\frac{1}{\alpha\log\alpha})}$, which is almost as bad as general
graphs. Therefore [BFN19] suggested studying a weaker gurantee provided by
tree covers. Here the goal is to construct a small collection of dominating
embeddings into trees such that every pair of vertices has a small distortion
in some tree in the collection. For $n$-vertex minor-free graph [BFN19]
constructed $1+\epsilon$ tree covers of size
$O_{r}(\frac{\log^{2}n}{\epsilon^{2}})$ (or a $O(1)$-tree cover $O(1)$ size).
For metrics with doubling dimension $d$, [BFN19] constructed $1+\epsilon$-tree
covers of size $(\frac{1}{\epsilon})^{O(d)}$. Recently, the authors [FL21]
showed that for doubling metrics, we can replace the trees by ultrametrics.

Minor free graphs. Different types of embedding were studied for minor-free
graphs. $K_{r}$-minor-free graphs embed into $\ell_{p}$ space with
multiplicative distortion $O_{r}(\log^{\min\\{\frac{1}{2},\frac{1}{p}\\}}n)$
[Rao99, KLMN05, AGG+19, AFGN18]. In particular, they embed into
$\ell_{\infty}$ of dimension $O_{r}(\log^{2}n)$ with a constant multiplicative
distortion. They also admit spanners with multiplicative distortion
$1+\epsilon$ and $\tilde{O}_{r}(\epsilon^{-3})$ lightness [BLW17]. On the
other hand, there are other graph families that embed well into bounded
treewidth graphs. Talwar [Tal04] showed that graphs with doubling dimension
$d$ and aspect ratio $\Phi$ ${}^{\ref{foot:aspectRatio}}$, stochastically
embed into graphs with treewidth $\epsilon^{-O(d\log d)}\cdot\log^{d}\Phi$
with expected distortion $1+\epsilon$. Similar embeddings are known for graphs
with highway dimension $h$ [FFKP18] (into treewidth
$(\log\Phi)^{-O(\log^{2}\frac{h}{\epsilon})}$ graphs), and graphs with
correlation dimension $k$ [CG12] (into treewidth
$\tilde{O}_{k,\epsilon}(\sqrt{n})$ graphs).

##  2 Preliminaries

$\tilde{O}$ notation hides poly-logarithmic factors, that is
$\tilde{O}(g)=O(g)\cdot\mathrm{polylog}(g)$, while $O_{r}$ notation hides
factors in $r$, e.g. $O_{r}(m)=O(m)\cdot f(r)$ for some function $f$ of $r$.
All logarithms are at base $2$ (unless specified otherwise).

We consider connected undirected graphs $G=(V,E)$ with edge weights
$w_{G}:E\to\mathbb{R}_{\geq 0}$. A graph is called unweighted if all its edges
have unit weight. Additionally, we denote $G$’s vertex set and edge set by
$V(G)$ and $E(G)$, respectively. Often, we will abuse notation and write $G$
instead of $V(G)$. $d_{G}$ denotes the shortest path metric in $G$, i.e.,
$d_{G}(u,v)$ is the shortest distance between $u$ to $v$ in $G$. Note that
every metric space can be represented as the shortest path metric of a
weighted complete graph. We will use the notions of metric spaces, and
weighted graphs interchangeably. When the graph is clear from the context, we
might use $w$ to refer to $w_{G}$, and $d$ to refer to $d_{G}$. $G[S]$ denotes
the induced subgraph by $S$. The diameter of $S$, denoted by
$\mathrm{diam}(S)$, is $\max_{u,v\in S}d_{G[S]}(u,v)$. 999This is often called
_strong_ diameter. A related notion is the _weak_ diameter of a cluster $S$ ,
defined to be $\max_{u,v\in S}d_{G}(u,v)$. Note that for a metric space, weak
and strong diameters are equivalent.

An ultrametric $\left(X,d\right)$ is a metric space satisfying a strong form
of the triangle inequality, that is, for all $x,y,z\in X$,
$d(x,z)\leq\max\left\\{d(x,y),d(y,z)\right\\}$. The following definition is
known to be an equivalent one (see [BLMN05b]).

######  Definition 1.

An ultrametric is a metric space $\left(X,d\right)$ whose elements are the
leaves of a rooted labeled tree $T$. Each $z\in T$ is associated with a label
$\ell\left(z\right)\geq 0$ such that if $x\in T$ is a descendant of $z$ then
$\ell\left(x\right)\leq\ell\left(z\right)$ and $\ell\left(x\right)=0$ iff $x$
is a leaf. The distance between leaves $x,y\in X$ is defined as
$d_{T}(x,y)=\ell\left(\mbox{lca}\left(x,y\right)\right)$ where
$\mbox{lca}\left(x,y\right)$ is the least common ancestor of $x$ and $y$ in
$T$.

###  2.1 Metric Embeddings

Classically, a metric embedding is defined as a function $f:X\rightarrow Y$
between the points of two metric spaces $(X,d_{X})$ and $(Y,d_{Y})$. A metric
embedding $f$ is said to be _dominating_ if for every pair of points $x,y\in
X$, it holds that $d_{X}(x,y)\leq d_{Y}(f(x),f(y))$. The distortion of a
dominating embedding $f$ is $\max_{x\not=y\in
X}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}$. Here we will study a more permitting
generalization of metric embedding introduced by Cohen-Addad et al. [CFKL20],
which is called _one-to-many_ embedding .

######  Definition 2 (One-to-many embedding).

A _one-to-many embedding_ is a function $f:X\rightarrow 2^{Y}$ from the points
of a metric space $(X,d_{X})$ into non-empty subsets of points of a metric
space $(Y,d_{Y})$, where the subsets $\\{f(x)\\}_{x\in X}$ are disjoint.
$f^{-1}(x^{\prime})$ denotes the unique point $x\in X$ such that
$x^{\prime}\in f(x)$. If no such point exists, $f^{-1}(x^{\prime})=\emptyset$.
A point $x^{\prime}\in f(x)$ is called a _copy_ of $x$, while $f(x)$ is called
the _clan_ of $x$. For a subset $A\subseteq X$ of vertices, denote
$f(A)=\cup_{x\in A}f(x)$.

We say that $f$ is _dominating_ if for every pair of points $x,y\in X$, it
holds that $d_{X}(x,y)\leq\min_{x^{\prime}\in f(x),y^{\prime}\in
f(y)}d_{Y}(x^{\prime},y^{\prime})$. We say that $f$ has multiplicative
distortion $t$, if it is dominating and $\forall x,y\in X$, it holds that
$\max_{x^{\prime}\in f(x),y^{\prime}\in f(y)}d_{Y}(x^{\prime},y^{\prime})\leq
t\cdot d_{X}(x,y)$. Similarly, $f$ has additive distortion $\epsilon D$ if $f$
is dominating and $\forall x,y\in X$, $\max_{x^{\prime}\in f(x),y^{\prime}\in
f(y)}d_{Y}(x^{\prime},y^{\prime})\leq d_{X}(x,y)+\epsilon D$.

A stochastic one-to-many embedding is a distribution $\mathcal{D}$ over
dominating one-to-many embeddings. We say that a stochastic one-to-many
embedding has expected multiplicative distortion $t$ if $\forall x,y\in X$,
$\mathbb{E}[\max_{x^{\prime}\in f(x),y^{\prime}\in
f(y)}d_{Y}(x^{\prime},y^{\prime})]\leq t\cdot d_{X}(u,v)$. Similarly, $f$ has
expected additive distortion $\epsilon D$, if $\forall x,y\in X$,
$\mathbb{E}[\max_{x^{\prime}\in f(x),y^{\prime}\in
f(y)}d_{Y}(x^{\prime},y^{\prime})]\leq d_{X}(x,y)+\epsilon D$.

For a one-to-many embedding $f$ between weighted graphs $G=(V,E,w)$ and
$H=(V^{\prime},E^{\prime},w^{\prime})$, we say that $f$ is spanning if
$V^{\prime}=f(V)$ (i.e. $f$ is “onto”), and for every edge $(u,v)\in
E^{\prime}$, it holds that $\left(f^{-1}(u),f^{-1}(v)\right)\in E$ and
$w^{\prime}(u,v)=w\left(f^{-1}(u),f^{-1}(v)\right)$.

This paper is mainly devoted to the new notion of clan embeddings.

######  Definition 3 (Clan embedding).

A clan embedding from metric space $(X,d_{X})$ into a metric space $(Y,d_{Y})$
is a pair $(f,\chi)$ where $f:X\rightarrow 2^{Y}$ is a dominating one-to-many
embedding, and $\chi:X\rightarrow Y$ is a classic embedding. For every $x\in
X$, we have that $\chi(x)\in f(x)$; here $f(x)$ called the clan of $x$, while
$\chi(x)$ is referred to as the chief of the clan of $x$ (or simply the chief
of $x$).

We say that clan embedding $f$ has multiplicative distortion $t$ if for every
$x,y\in X$, $\min_{y^{\prime}\in f(y)}d_{Y}(y^{\prime},\chi(x))\leq t\cdot
d_{X}(x,y)$. Similarly, $f$ has additive distortion $\epsilon D$ if for every
$x,y\in X$, $\min_{y^{\prime}\in f(y)}d_{Y}(y^{\prime},\chi(x))\leq
d_{X}(x,y)+\epsilon D$.

A clan embedding $(f,\chi)$ is said to be spanning if $f$ is a spanning one-
to-many embedding.

We will construct embeddings for minor-free graphs using a divide-and-concur
approach. First, we will construct embedding on each piece (see below). Then,
in order to combine different embeddings into a single one, it will be
important that these embeddings are _clique-preserving_.

######  Definition 4 (Clique-copy).

Consider a one-to-many embedding $f:G\rightarrow 2^{H}$, and a clique $Q$ in
$G$. A subset $Q^{\prime}\subseteq f(Q)$ is called clique copy of $Q$ if
$Q^{\prime}$ is a clique in $H$, and for every vertex $v\in Q$,
$Q^{\prime}\cap f(v)$ is a singleton.

######  Definition 5 (Clique-preserving embedding).

A one-to-many embedding $f:G\rightarrow 2^{H}$ is called clique-preserving
embedding if for every clique $Q$ in $G$, $f(Q)$ contains a clique copy of
$Q$. A clan embedding $(f,\chi)$ is clique-preserving if $f$ is clique
preserving.

###  2.2 Robertson-Seymour Structure Theorem

In this section, we review notation used in graph minor theory by Robertson
and Seymour. Informally speaking, the celebrated theorem of Robertson and
Seymour (Theorem 9, [RS03]) said that every minor-free graph can be decomposed
into a collection of graphs _nearly embeddable_ in the surface of constant
genus, glued together into a tree structure by taking _clique-sum_. To
formally state the Robertson-Seymour decomposition, we need additional
notation.

######  Definition 6 (Tree/Path decomposition).

A tree decomposition of $G(V,E)$, denoted by $\mathcal{T}$, is a tree
satisfying the following conditions:

  1. 1.

Each node $i\in V(\mathcal{T})$ corresponds to a subset of vertices $X_{i}$ of
$V$ (called bags), such that $\cup_{i\in V(\mathcal{T})}X_{i}=V$.

  2. 2.

For each edge $uv\in E$, there is a bag $X_{i}$ containing both $u,v$.

  3. 3.

For a vertex $v\in V$, all the bags containing $v$ make up a subtree of
$\mathcal{T}$.

The _width_ of a tree decomposition $\mathcal{T}$ is $\max_{i\in
V(\mathcal{T})}|X_{i}|-1$ and the treewidth of $G$, denoted by $\mathrm{tw}$,
is the minimum width among all possible tree decompositions of $G$. A _path
decomposition_ of a graph $G(V,E)$ is a tree decomposition where the
underlying tree is a path. The pathwidth of $G$, denoted by $\mathrm{pw}$, is
defined accordingly.

A _vortex_ is a graph $W$ equipped with a pah decomposition
$\\{X_{1},X_{2},\ldots,X_{t}\\}$ and a sequence of $t$ designated vertices
$x_{1},\ldots,x_{t}$, called the _perimeter_ of $W$, such that each $x_{i}\leq
X_{i}$ for all $1\leq i\leq t$. The _width_ of the vortex is the width of its
path decomposition. We say that a vortex $W$ is _glued_ to a face $F$ of a
surface embedded graph $G$ if $W\cap F$ is the perimeter of $W$ whose vertices
appear consecutively along the boundary of $F$.

##### Nearly $h$-embeddability

A graph $G$ is nearly $h$-embeddable if there is a set of at most $h$ vertices
$A$, called _apices_ , such that $G\setminus A$ can be decomposed as
$G_{\Sigma}\cup\\{W_{1},W_{2},\ldots,W_{h}\\}$ where $G_{\Sigma}$ is
(cellularly) embedded on a surface $\Sigma$ of genus at most $h$ and each
$W_{i}$ is a vortex of width at most $h$ glued to a face of $G_{\Sigma}$.

#####  $h$-Clique-sum

A graph $G$ is a $h$-clique-sum of two graphs $G_{1},G_{2}$, denoted by
$G=G_{1}\oplus_{h}G_{2}$, if there are two cliques of size exactly $h$ each
such that $G$ can be obtained by identifying vertices of the two cliques and
remove some clique edges of the resulting identification.

Note that clique-sum is not a well-defined operation since the clique-sum of
two graphs is not unique due to the clique edge deletion step. We are ready
now to state the decomposition theorem.

######  Theorem 9 (Theorem 1.3 [RS03]).

There is a constant $h=O_{r}(1)$ such that any $K_{r}$-minor-free graph $G$
can be decomposed into a tree $\mathbb{T}$ where each node of $\mathbb{T}$
corresponds to a nearly $h$-embeddable graph such that $G=\cup_{X_{i}X_{j}\in
E(\mathbb{T})}X_{i}\oplus_{h}X_{j}$.

The graphs corresponding to the nodes in the clique-sum decomposition above
are referred to as _pieces_. Note that the pieces in $\mathbb{T}$ may not be
subgraphs of $G$, as in the clique-sum, some edges of a node, namely some
edges of a nearly $h$-embeddable subgraph associated to a node, may not be
present in $G$. We will slightly modify the graph to ensure that this never
happens. Specifically, for any pair $u,v$ of vertices used in a clique-sum for
a piece $X$ of $\mathbb{T}$, that are not present in $G$, we add an edge
$(u,v)$ to $G$ and set its weight to be $d_{G}(u,v)$. In the decomposition of
the resulting graph, the clique-sum operation does not remove any edge. Note
that this operation does not change the Robertson-Seymour decomposition of the
graph, nor its shortest path metric. Thus from a metric point of view, the two
graphs are equivalent.

Cohen-Addad et al. [CFKL20] showed that every $n$-vertex $K_{r}$-minor free
graph has a stochastic one-to-many embedding with expected additive distortion
$\epsilon D$ into a graph with treewidth $O(\frac{\log n}{\epsilon^{2}})$. The
only reason [CFKL20] used randomness is due to apices. The following lemma
[CFKL20] states that nearly $h$-embeddable graphs without apices embed
deterministically into bounded treewidth graphs. We will use this embedding in
a black box manner.

######  Lemma 1 (Multiple Vortices and Genus, [CFKL20]).

Consider a graph $G=G_{\Sigma}\cup W_{1}\cup\dots\cup W_{h}$ of diameter $D$,
where $G_{\Sigma}$ is (cellularly) embedded on a surface $\Sigma$ of genus
$h$, and each $W_{i}$ is a vortex of width at most $h$ glued to a face of
$G_{\Sigma}$. There is a one-to-many clique-preserving embedding $f$ from $G$
to a graph $H$ of treewidth at most $O_{h}\left(\frac{\log
n}{\epsilon}\right)$ with additive distortion $\epsilon D$.

##  3 Clan embedding into an ultrametric

This section is devoted to proving Theorem 1. We restate it for convenience.
See 1

First, we will prove a “distributional” version of Theorem 1. That is, we will
receive a distribution $\mu$ over the points, and deterministically construct
a single clan embedding $(f,\chi)$ such that $\sum_{x\in X}\mu(x)|f(x)|$ will
be bounded. Later, we will use the minimax theorem to conclude Theorem 1. We
begin with some definitions: a _measure_ over a finite set $X$, is simply a
function $\mu:X\rightarrow\mathbb{R}_{\geq 0}$. The measure of a subset
$A\subseteq X$, is $\mu(A)=\sum_{x\in A}\mu(x)$. Given some function
$f:X\rightarrow\mathbb{R}$, it’s expectation w.r.t. $\mu$ is
$\mathbb{E}_{x\sim\mu}[f]=\sum_{x\in X}\mu(x)\cdot f(x)$. We say that $\mu$ is
a _probability measure_ if $\mu(X)=1$. We say that $\mu$ is a _$(\geq 1)$
-measure_ if for every $x\in X$, $\mu(x)\geq 1$.

######  Lemma 2.

Given an $n$-point metric space $(X,d_{X})$, $(\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 $16k$ such that
$\mathbb{E}_{x\sim\mu}[|f(x)|]\leq\mu(X)^{1+\frac{1}{k}}$.

_Proof._ Our proof is inspired by Bartal’s lecture notes [Bar11], who provided
a deterministic construction of Ramsey trees. Specifically, 1 bellow is due to
[Bar11]. Lemma 2 could also be proved using the techniques of Abraham et al.
[ACE+20] (and indeed we will use their approach for our clan embedding into a
spanning tree, see Lemma 5); however the proof based on [Bar11] we present
here is shorter. For a subset $A\subseteq X$, denote by $B_{A}(x,r)\coloneqq
B_{X}(x,r)\cap A$ the ball in the metric space $(X,d_{X})$ restricted to $A$.
Set $\mu^{*}(A)\coloneqq\max_{x\in
A}\mu\left(B_{A}(x,\frac{\mathrm{diam}(A)}{4})\right)$. Note that $\mu^{*}$ is
monotone: i.e. $A^{\prime}\subseteq A$ implies
$\mu^{*}(A^{\prime})\leq\mu^{*}(A)$, and $\forall A,$ $\mu^{*}(A)\leq\mu(A)$.
The following claim is crucial for our construction; its proof appears below.
See Figure 2 for an illustration of the claim.

######  Claim 1.

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}{8k}\cdot\mathrm{diam}(X))}$,
$Q=B_{X}(v,R)$, and $\bar{Q}=X\setminus Q$ satisfy
$\mu(P)\leq\mu(Q)\cdot\left(\frac{\mu^{*}(X)}{\mu^{*}(P)}\right)^{\frac{1}{k}}$.

The construction of the embedding is by induction on $n$, the number of points
in the metric space. We assume that for a metric space $X$ with strictly less
than $n$ points, and arbitrary $(\geq 1)$-measure $\mu$, we can construct a
clan embedding $(f,\chi)$ with distortion $16k$, such that
$\mathbb{E}_{x\sim\mu}[|f(x)|]\leq\mu(X)\mu^{*}(X)^{\frac{1}{k}}\leq\mu(X)^{1+\frac{1}{k}}$.
Find sets $P,Q,\bar{Q}\subseteq X$ using 1. Let $\mu_{P}$ (resp.
$\mu_{\bar{Q}}$) be the $(\geq 1)$-measure $\mu$ restricted to $P$ (resp.
$\bar{Q}$). Using the induction hypothesis, construct clan embeddings
$(f_{P},\chi_{P})$ for $P$, and $(f_{\bar{Q}},\chi_{\bar{Q}})$ for $\bar{Q}$
into ultra-metrics $U_{P},U_{\bar{Q}}$ respectively. Construct a new
ultrametric $U$ by combining $U_{P}$ and $U_{\bar{Q}}$ by adding a new root
node $r_{U}$ with label $\mathrm{diam}(X)$ and making roots of $U_{P}$ and
$U_{\bar{Q}}$ children of $r_{U}$. For every $x\in X$ set $f(x)=f_{P}(x)\cup
f_{\bar{Q}}(x)$. If $d_{X}(v,x)\leq R+\frac{1}{16k}\cdot\mathrm{diam}(X)$ set
$\chi(x)=\chi_{P}(x)$, otherwise set $\chi(x)=\chi_{\bar{Q}}(x)$. This
finishes the construction; see Figure 2 for an illustration.

Figure 2: On the left illustrated the clusters $P,Q,\bar{Q}$ from 1. On the
right we illustrate the clan embedding of the metric space $(X,d_{X})$ into
ultrametric $U$. $r_{U}$ is the root of $U$, and its children are the roots of
the ultrametrics $U_{P},U_{\bar{Q}}$ which were constructed recursively. The
point $x\in P\cap Q$ has $f(x)=f_{P}(x)$ and $\chi(x)=\chi_{P}(x)$ (where
$|f(x)|=2$). The point $y$ is in $\bar{Q}\setminus P$ and thus
$f(y)=f_{\bar{Q}}(y)$ and $\chi(y)=\chi_{\bar{Q}}(y)$ (there is a single copy
of $y$). The point $z$ belongs to $P\cap\bar{Q}$, where
$d_{X}(v,z)>R+\frac{1}{16}\cdot\mathrm{diam}(X)$, hence $f(z)=f_{P}(z)\cup
f_{\bar{Q}}(z)$ and $\chi(z)=\chi_{\bar{Q}}(z)$. Note that
$|f_{P}(z)|=|f_{\bar{Q}}(z)|=2$, and hence $|f(z)|=4$.

Next, we argue that the clan embedding $(f,\chi)$ has multiplicative
distortion $16k$. Consider a pair of points $x,y\in X$. We will show that
$\min_{y^{\prime}\in f(y)}d_{U}(y^{\prime},\chi(x))\leq 16k\cdot d_{X}(x,y)$.
Suppose first that $d_{X}(v,x)\leq R+\frac{1}{16k}\cdot\mathrm{diam}(X)$. If
$y\in P$, then by the induction hypothesis

$\min_{y^{\prime}\in f(y)}d_{U}(y^{\prime},\chi(x))\leq\min_{y^{\prime}\in
f_{P}(y)}d_{U_{P}}(y^{\prime},\chi_{P}(x))\leq 16k\cdot d_{P}(x,y)=16k\cdot
d_{X}(x,y)\leavevmode\nobreak\ .$

Else, $y\notin P$, then $d_{X}(v,y)>R+\frac{1}{8k}\cdot\mathrm{diam}(X)$.
Using the triangle inequality $d_{X}(x,y)\geq
d_{X}(v,y)-d_{X}(v,x)\geq\frac{\mathrm{diam}(X)}{16}$. Note that the label of
$r_{U}$ is $\mathrm{diam}(X)$, implying that $\min_{y^{\prime}\in
f(y)}d_{U}(y^{\prime},\chi(x))\leq\mathrm{diam}(X)\leq 16\cdot d_{X}(x,y)$.
The case where $d_{X}(v,x)>R+\frac{1}{16k}\cdot\mathrm{diam}(X)$ is symmetric
(using $\bar{Q}$ instead of $P$).

Next, we bound the weighted number of leafs in the ultrametric. Note that the
process is deterministic and there is no probability involved. Using the
induction hypothesis, it holds that

$\displaystyle\mathbb{E}_{x\sim\mu}[|f(x)|]$ $\displaystyle=\sum_{x\in
X}\mu(x)\cdot\left(|f_{P}(x)|+|f_{\bar{Q}}(x)|\right)$
$\displaystyle=\mathbb{E}_{x\sim\mu_{P}}[|f_{P}(x)|]+\mathbb{E}_{x\sim\mu_{\bar{Q}}}[|f_{\bar{Q}}(x)|]$
$\displaystyle\leq\mu_{P}(P)\mu_{P}^{*}(P)^{\frac{1}{k}}+\mu_{\bar{Q}}(\bar{Q})\mu_{\bar{Q}}^{*}(\bar{Q})^{\frac{1}{k}}$
$\displaystyle\leq\mu(P)\mu^{*}(P)^{\frac{1}{k}}+\mu(\bar{Q})\mu^{*}(\bar{Q})^{\frac{1}{k}}$
$\displaystyle\overset{(*)}{\leq}\mu(Q)\mu^{*}(X)^{\frac{1}{k}}+\mu(\bar{Q})\mu^{*}(X)^{\frac{1}{k}}=\mu(X)\mu^{*}(X)^{\frac{1}{k}}\leavevmode\nobreak\
,$

where in the inequality $(*)$ is due to 1 and the fact that
$\mu^{*}(\bar{Q})\leq\mu^{*}(X)$. ∎

###### Proof of 1.

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)}{8k}$, and for $i\in[0,k]$ let
$Q_{i}=B_{X}(v,\frac{\mathrm{diam}(X)}{8}+i\cdot\rho)$. Let $i\in[0,k-1]$ be
the index minimizing $\frac{\mu(Q_{i+1})}{\mu(Q_{i})}$. Then,

$\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+1})}{\mu(Q_{i})}\right)^{k\cdot\frac{1}{k}}=\frac{\mu(Q_{i+1})}{\mu(Q_{i})}\leavevmode\nobreak\
.$

Set $R=\frac{\mathrm{diam}(X)}{8}+i\cdot\rho$, then $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\cdot\rho)=\frac{\mathrm{diam}(X)}{2}$. 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$. ∎

Next, we translate the language of $(\geq 1)$-measures used in Lemma 2 to
probability measures:

######  Lemma 3.

Given an $n$-point metric space $(X,d_{X})$, and probability measure
$\mu:X\rightarrow\mathbb{R}_{\geq 0}$, we can construct the two following clan
embeddings $(f,\chi)$ into ultrametrics:

  1. 1.

For every parameter $k\geq 1$, multiplicative distortion $16k$ such that
$\mathbb{E}_{x\sim\mu}[|f(x)|]\leq O(n^{\frac{1}{k}})$.

  2. 2.

For every parameter $\epsilon\in(0,1]$, multiplicative distortion
$O(\frac{\log n}{\epsilon})$ such that $\mathbb{E}_{x\sim\mu}[|f(x)|]\leq
1+\epsilon$.

###### Proof.

We define the following probability measure $\widetilde{\mu}$: $\forall x\in
X$, $\widetilde{\mu}(x)=\frac{1}{2n}+\frac{1}{2}\mu(x)$. Set the following
$(\geq 1)$-measure $\widetilde{\mu}_{\geq 1}(x)=2n\cdot\tilde{\mu}(x)$. Note
that $\widetilde{\mu}_{\geq 1}(X)=2n$. We execute Lemma 2 w.r.t. the $(\geq
1)$-measure $\widetilde{\mu}_{\geq 1}$, and parameter
$\frac{1}{\delta}\in\mathbb{N}$ to be determined later. It holds that

$\widetilde{\mu}_{\geq
1}(X)\cdot\mathbb{E}_{x\sim\widetilde{\mu}}[|f(x)|]=\mathbb{E}_{x\sim\widetilde{\mu}_{\geq
1}}[|f(x)|]\leq\widetilde{\mu}_{\geq 1}(X)^{1+\delta}=\widetilde{\mu}_{\geq
1}(X)\cdot(2n)^{\delta}\leavevmode\nobreak\ ,$

implying

$(2n)^{\delta}\geq\mathbb{E}_{x\sim\widetilde{\mu}}[|f(x)|]=\frac{1}{2}\cdot\mathbb{E}_{x\sim\mu}[|f(x)|]+\frac{\sum_{x\in
X}|f(x)|}{2n}\geq\frac{1}{2}\cdot\mathbb{E}_{x\sim\mu}[|f(x)|]+\frac{1}{2}\leavevmode\nobreak\
.$

  1. 1.

Set $\delta=\frac{1}{k}$, then we have multiplicative distortion
$\frac{16}{\delta}=16k$, and $\mathbb{E}_{x\sim\mu}[|f(x)|]\leq
2\cdot(2n)^{\delta}=O(n^{\frac{1}{k}})$.

  2. 2.

Choose $\delta\in(0,1]$ such that
$\frac{1}{\delta}=\left\lceil\frac{\ln(2n)}{\ln(1+\epsilon/2)}\right\rceil$,
note that $\delta\leq\frac{\ln(1+\epsilon/2)}{\ln(2n)}$. Then we have
multiplicative distortion $O(\frac{1}{\delta})=O(\frac{\log n}{\epsilon})$,
and $\mathbb{E}_{x\sim\mu}[|f(x)|]\leq 2\cdot(2n)^{\delta}-1\leq 1+\epsilon$.

∎

######  Remark 1.

Lemma 3, note that for the clan embedding $(f,\chi)$ returned by Lemma 3 for
input $k$, it holds that $|f(X)|\leq\tilde{\mu}_{\geq
1}(X)^{1+\frac{1}{k}}=(2n)^{1+\frac{1}{k}}$. In particular, every $x\in X$ has
at most $(2n)^{1+\frac{1}{k}}$ copies. Similarly, for input $\epsilon$,
$|f(X)|\leq\tilde{\mu}_{\geq
1}(X)^{1+\delta}\leq(2n)^{1+\frac{\ln(1+\epsilon/2)}{\ln
2n}}=2n\cdot(1+\frac{\epsilon}{2})$. As for every $y\in X$,
$f(y)\neq\emptyset$, it follows that for every $x\in X$, its number of copies
is bounded by $|f(x)|=|f(X)|-|f(X\setminus\\{x\\})|\leq
2n\cdot(1+\frac{\epsilon}{2})-(n-1)=(1+\epsilon)n+1$.

Using the minimax theorem, as shown bellow, we show that there exists a
distribution $\mathcal{D}$ of clan embeddings with distortion and expected
clan size as specified by Theorem 1. Afterwards, in Section 3.1, using the
multiplicative weights update (MWU) method, we explicitly construct such
distributions efficiently, and with small support size.

###### Proof of Theorem 1 (exsistential agrument).

Let $\mu$ be an arbitrary probability measure over the points, and
$\mathcal{D}$ be any distribution over clan embeddings $(f,\chi)$ of
$(X,d_{X})$ intro trees with multiplicative distortion $O(\frac{\log
n}{\epsilon})$. Using Lemma 3 and the minimax theorem we have that

$\min_{\mathcal{D}}\max_{\mu}\mathbb{E}_{(f,\chi)\sim\mathcal{D},x\sim\mu}[|f(x)|]=\max_{\mu}\min_{(f,\chi)}\mathbb{E}_{x\sim\mu}[|f(x)|]\leq
1+\epsilon\leavevmode\nobreak\ .$

Let $\mathcal{D}$ be the distribution from above, denote by $\mu_{z}$ the
probability measure where $\mu_{z}(z)=1$ (and $\mu_{z}(y)=0$ for $y\neq z$).
Then for every $x\in X$

$\mathbb{E}_{(f,\chi)\sim\mathcal{D}}[|f(z)|]=\mathbb{E}_{(f,\chi)\sim\mathcal{D},x\sim\mu_{z}}[|f(x)|]\leq\max_{\mu}\mathbb{E}_{(f,\chi)\sim\mathcal{D},x\sim\mu}[|f(x)|]\leq
1+\epsilon\leavevmode\nobreak\ .$

The second claim of Theorem 1 could be proven using exactly the same argument.
∎

###  3.1 Constructive Proof of Theorem 1

In this section, we efficiently construct a uniform distribution $\mathcal{D}$
as stated in Theorem 1. Our construction relies on the multiplicative weights
update method (MWU) 101010For an excellent introduction of the MWU method and
its historical account, see the survey by Arora, Hazan and Kale [AHK12]. and
the notion of a $(\rho,\alpha,\beta)$-bounded Oracle.

######  Definition 7 ($(\rho,\alpha,\beta)$-bounded Oracle).

Given a probability measure $\mu$ over the metric points, a
$(\rho,\alpha,\beta)$-bounded Oracle returns a clan embedding $(f,\chi)$ with
multiplicative distortion $\beta$ such that:

  1. 1.

$\mathbb{E}_{x\sim\mu}[|f(x)|]\leq\alpha$.

  2. 2.

$\max_{x\in V}|f(x)|\leq\rho$.

In Lemma 4 below, we show that one can construct a uniform distribution
$\mathcal{D}$ by making a polynomial number of oracle calls.

######  Lemma 4.

Given a $(\rho,\alpha,\beta)$-bounded Oracle, and parameter
$\epsilon\in(0,\frac{1}{2})$ one can construct a uniform distribution
$\mathcal{D}$ over $O(\frac{\rho\alpha\log(n)}{\epsilon^{2}})$ clan embeddings
with multiplicative distortion $\beta$ such that:

$\mbox{For every }x\in X,\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{E}_{(f,\chi)\sim\mathcal{D}}[|f(x)|]\leq\alpha+\epsilon$

Furthermore, the construction only makes
$O(\frac{\rho\alpha\log(n)}{\epsilon^{2}})$ queries to the
$(\rho,\alpha,\beta)$-bounded Oracle.

###### Proof.

Let $\mathcal{O}$ be a $(\rho,\alpha,\beta)$-bounded Oracle and
$\mathcal{O}(\mu)$ be the clan embedding returned by the oracle given a
probability measure $\mu$. We follow the standard set up of MWU: we have $n$
“experts” where the $i$-th expert is associated with the $i$-th point
$x_{i}\in X$. The construction happens in $T$ rounds. At the beginning of
round $t$, we have a weight vector
$\mathbf{w}^{t}=(w_{1}^{t},\ldots,w_{n}^{t})^{\intercal}$; at the first round,
$\mathbf{w}^{1}=(1,1,\ldots,1)^{\intercal}$.

The weight vector $\mathbf{w}^{t}$ induces a probability measure
$\mu^{t}=(\frac{w^{t}_{1}}{W^{t}},\ldots,\frac{w^{t}_{n}}{W^{t}})$ where
$W^{t}=\sum_{i=1}^{n}w^{t}_{i}$. We construct a clan embedding
$(f^{t},\chi^{t})=\mathcal{O}(\mu^{t})$ by making an oracle call to
$\mathcal{O}$ with $\mu_{t}$ as input. Let
$g^{t}_{i}=\frac{|f^{t}(x_{i})|}{\rho}$, and
$\mathbf{g}^{t}=(g^{t}_{1},\ldots,g^{t}_{n})^{\intercal}$ be the “penalty”
vector for the set of $n$ points (or experts). We then update:

$w^{t+1}_{i}=(1+\delta)^{g^{t}_{i}}w^{t}_{i}\qquad\forall x_{i}\in X,$ (1)

for some small parameter $\delta$ chosen later.

The penalty for each additional copy of each point is proportional to the
number of copies it has in the clan embeddings constructed in previous steps.
This is because in the next round, we will increase the measure of points with
a large number of copies. Hence the oracle will be “motivated” to reduce the
number of copies of these points in the next outputted clan embedding.

After $T$ rounds, we have a collection
$\mathcal{D}_{T}=\\{(f^{1},\chi^{1}),\ldots,(f^{T},\chi^{T})\\}$ of $T$ clan
embeddings. The distribution $\mathcal{D}$ is constructed by sampling an
embedding from $\mathcal{D}_{T}$ uniformly at random. Note that the distortion
bound follows directly from the fact that the distortion of every clan
embedding returned by the oracle is $\beta$. Our goal is to show that, by
setting $T=O(\frac{\rho\log(n)}{\epsilon^{2}})$, we have:

$\frac{1}{T}\cdot\sum_{t=1}^{T}|f^{t}(x_{i})|\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \alpha+\epsilon\qquad\forall x_{i}\in V$ (2)

To that end, we first observe that:

$W^{t+1}\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{i=1}^{n}w_{i}^{t+1}\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{i=1}^{n}(1+\delta)^{g_{i}^{t}}w_{i}^{t}\leavevmode\nobreak\
\stackrel{{\scriptstyle(*)}}{{\leq}}\leavevmode\nobreak\
\sum_{i=1}^{n}(1+\delta g_{i}^{t})w_{i}^{t}\leavevmode\nobreak\
=\leavevmode\nobreak\ (1+\sum_{i=1}^{n}\delta
g_{i}^{t}\mu_{i}^{t})W^{t}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
e^{\delta\langle\mathbf{g}^{t},\mu^{t}\rangle}W^{t}$

where inequality $(*)$ follows from that $(1+x)^{r}\leq(1+rx)$ for any $x\geq
0$ and $r\in[0,1]$. Thus, we have:

$W^{T+1}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
e^{\delta\sum_{t=1}^{T}\langle\mathbf{g}^{t},\mu^{t}\rangle}W^{1}\leavevmode\nobreak\
=\leavevmode\nobreak\
e^{\delta\sum_{t=1}^{T}\langle\mathbf{g}^{t},\mu^{t}\rangle}n$ (3)

Observe that $W^{T+1}\geq
w^{T+1}_{i}=(1+\delta)^{\sum_{t=1}^{T}g^{t}_{i}}w^{1}_{i}=(1+\delta)^{\sum_{t=1}^{T}g^{t}_{i}}$
and that:

$\sum_{t=1}^{T}\langle\mathbf{g}^{t},\mu^{t}\rangle\leavevmode\nobreak\
=\leavevmode\nobreak\ \sum_{t=1}^{T}\sum_{x\in
X}\frac{|f^{t}(x)|}{\rho}\cdot\mu^{t}(v_{i})\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{1}{\rho}\cdot\sum_{t=1}^{T}\mathbb{E}_{x\sim\mu^{t}}[|f^{t}(x)|]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{T\alpha}{\rho}\leavevmode\nobreak\ .$

Thus, by equation (3), it holds that:

$\displaystyle(1+\delta)^{\sum_{t=1}^{T}g^{t}_{i}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ e^{\frac{\delta T\alpha}{\rho}}n\leavevmode\nobreak\
.$ (4)

Taking the natural logarithm from both sides we obtain that $\frac{\delta
T\alpha}{\rho}+\ln
n\geq\sum_{t=1}^{T}g_{i}^{t}\cdot\ln(1+\delta)=\frac{\ln(1+\delta)}{\rho}\cdot\sum_{t=1}^{T}|f^{t}(x_{i})|$,
and thus

$\frac{1}{T}\cdot\sum_{t=1}^{T}|f^{t}(x_{i})|\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{\rho}{T\cdot\ln(1+\delta)}\cdot\left(\frac{\delta T\alpha}{\rho}+\ln
n\right)\leavevmode\nobreak\ =\leavevmode\nobreak\
\frac{\delta\alpha}{\ln(1+\delta)}+\frac{\rho\cdot\ln
n}{T\cdot\ln(1+\delta)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\alpha(1+\frac{\delta}{2})+\frac{2\rho\cdot\ln
n}{T\cdot\delta}\leavevmode\nobreak\ ,$

where the last inequality follows as
$\frac{\delta}{\ln(1+\delta)}\leq(1+\frac{\delta}{2})$ and
$\ln(1+\delta)\geq\frac{\delta}{2}$ for $\delta\in(0,\frac{1}{2})$. By
choosing $T=\frac{4\rho\alpha\ln n}{\epsilon^{2}}=O(\frac{\rho\alpha\log
n}{\epsilon^{2}})$ and $\delta=\sqrt{\frac{4\rho\ln
n}{T\alpha}}=\sqrt{\frac{\epsilon^{2}}{\alpha^{2}}}=\frac{\epsilon}{\alpha}<\frac{1}{2}$,
we obtain that

$\frac{1}{T}\cdot\sum_{t=1}^{T}|f^{t}(x_{i})|\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\alpha+\frac{\delta\cdot\alpha}{2}+\frac{\epsilon^{2}}{2\alpha\cdot\delta}\leavevmode\nobreak\
=\leavevmode\nobreak\ \alpha+\epsilon\leavevmode\nobreak\ ,$

satisfying equation (2), which completes our proof. ∎

Observe that Lemma 3, combined with Remark 1, provides an
$(O(n),1+\frac{\epsilon}{2},O(\frac{\log n}{\epsilon}))$-bounded Oracle (when
we apply Lemma 3 with parameter $\frac{\epsilon}{2}$). Using Lemma 4 with
parameter $\frac{\epsilon}{2}$ provides us with an efficiently computable
distribution over clan embeddings with support size $O(\frac{n\log
n}{\epsilon^{2}})$, distortion $O(\frac{\log n}{\epsilon})$, and such that for
every $x\in X$, $\mathbb{E}_{(f,\chi)\sim\mathcal{D}}[|f(x)|]\leq 1+\epsilon$.

Similarly, by applying Lemma 3 with parameter $k$, we get an
$(O(n^{1+\frac{1}{k}}),O(n^{\frac{1}{k}}),16k)$-bounded Oracle. Thus Lemma 4
will produce an efficiently computable distribution over clan embeddings with
support size $O(n^{1+\frac{2}{k}}\log n)$, distortion $16k$, and such that for
every $x\in X$,
$\mathbb{E}_{(f,\chi)\sim\mathcal{D}}[|f(x)|]=O(n^{\frac{1}{k}})$. Theorem 1
now follows.

##  4 Clan Embedding into a Spanning Tree

This section is devoted to proving Theorem 3. We restate it for convenience.

See 3

In this section, we construct spanning clan embeddings into trees. We will use
the framework of petal decomposition proposed by Abraham and Neiman [AN19],
who originally used it to construct a stochastic embedding of a graph into
spanning trees with a bounded expected distortion. The framework was also
previously used by Abraham et al. [ACE+20] to construct Ramsey spanning trees.
The petal decomposition is an iterative method to build a spanning tree of a
given graph. At each level, the current graph is partitioned into smaller
diameter pieces (called _petals_), and a single central piece (called
_stigma_), which are then connected by edges in a tree structure. Each of the
petals is a ball in a certain cone metric. When creating a petal from a
cluster of diameter $\Delta$, one has the freedom to choose a radius from an
interval of length $\Omega(\Delta)$. The crucial property is that, regardless
of the radii choices during the execution of the algorithm, the framework
guarantees that the diameter of the resulting tree will be $O(\Delta)$.

However, as we are constructing a clan embedding rather than a classical one,
some vertices will have multiple copies. As a result, some mild changes will
be introduced to the construction of [AN19]. Once we establish the petal
decomposition framework for clan embeddings, the proof of Theorem 3 will
follow the lines similar to Theorem 1. The additional $\log\log n$ factor is a
phenomenon also appearing in previous uses of the petal decomposition
framework [AN19, ACE+20]. The reason is that, while similar embeddings into
ultrametrics create clusters by growing balls around smartly chosen centers
(e.g. [Bar04, Bar11] and Theorem 1), in the petal decomposition framework, we
lack the freedom to choose the center of the petal.

##### Organization:

In Section 4.1, we describe the petal decomposition framework in general. In
Section 4.2, we describe our specific usage of it, i.e. the algorithm choosing
the radii (with some leftovers in Section 4.4). Then in Section 4.3, we prove
Lemma 5, that appears below. Lemma 5 is a “distributional” version of Theorem
3, and has a role parallel to Lemma 2 in Section 3. Finally, in Section 4.5,
we will deduce Theorem 3 using Lemma 5.

######  Lemma 5.

Given an $n$-vertex weighted graph $G=(V,E,w)$, $(\geq 1)$-measure
$\mu:V\rightarrow\mathbb{R}_{\geq 1}$, and integer parameter $k\geq 1$, there
is a spanning clan embedding $(f,\chi)$ into a tree with multiplicative
distortion $O(k\log\log\mu(V))$ such that
$\mathbb{E}_{v\sim\mu}[|f(v)|]\leq\mu(V)^{1+\frac{1}{k}}$.

###  4.1 Petal Decomposition Framework

We begin with some notations specific to this section. For a subset
$S\subseteq G$ and a center vertex $x_{0}\in S$, the radius of $S$ w.r.t
$x_{0}$, $\Delta_{x_{0}}(S)$, is the minimal $\Delta$ such that
$B_{G[S]}(x_{0},\Delta)=S$. (If for every $\Delta$,
$B_{G[S]}(x_{0},\Delta)\neq S$ — this can happen iff $G[S]$ is not connected —
we say that $\Delta_{x_{0}}(S)=\infty$.) When the center $x_{0}$ is clear from
the context or is not relevant, we will omit it. Given two vertices $u,v$,
$P_{u,v}(X)$ denotes the shortest path between them in $G[X]$, the graph
induced by $X$ (we will assume that every pair has a unique shortest path;
this can be arranged by tiny perturbation of the edge weights.).

Given a graph $G=(V,E,w)$ and a cluster $A\subseteq V$ (with center $x_{0}$),
we say that a vertex $y\in A$ is $\rho$-padded by the cluster
$A^{\prime}\subseteq A$ (w.r.t $A$) if $B(y,\Delta_{x_{0}}(A)/\rho,G)\subseteq
A^{\prime}$. See an illustration on the right.

Next, we provide a concise description of the petal decomposition algorithm,
focusing on the main properties we will use. For proofs and further details,
we refer readers to [AN19]. The presentation here differs slightly from [AN19]
as our goal is to construct a spanning clan embedding into a tree rather than
a classic one. However, the changes are straightforward, and no new ideas are
required.

The hierarchical-petal-decomposition (see Algorithm 1) is a recursive
algorithm. The input is $G[X]$ (a graph $G=(V,E,w)$ induced over a set of
vertices $X\subseteq V$), a center $x_{0}\in X$, a target $t\in X$, and the
radius $\Delta=\Delta_{x_{0}}(X)$.111111Rather than inferring
$\Delta=\Delta_{x_{0}}(X)$ from $G[X]$ and $x_{0}$ as in [AN19], we will
follow [ACE+20] and think of $\Delta$ as part of the input. We shall allow any
$\Delta\geq\Delta_{x_{0}}(X)$. We stress that, in fact, in the algorithm, we
always use $\Delta_{x_{0}}(X)$, and consider this degree of freedom only in
the analysis. The algorithm invokes the petal-decomposition procedure to
create clusters $\widetilde{X}_{0},\widetilde{X}_{1},\dots,\widetilde{X}_{s}$
of $X$ (for some integer $s$), and also provides a set of edges
$\\{(x_{1},y_{1}),\dots,(x_{s},y_{s})\\}$ and targets
$t_{0},t_{1},\dots,t_{s}$. The hierarchical-petal-decomposition algorithm now
recurses on each
$(G[\widetilde{X}_{j}],x_{j},t_{j},\Delta_{x_{j}}(\widetilde{X}_{j}))$ for
$0\leq j\leq s$, to get trees $\\{T_{j}\\}_{0\leq j\leq s}$ (and clan
embeddings $\\{(f_{j},\chi_{j})\\}_{0\leq j\leq s}$), which are then connected
by the edges $\\{(x_{j},y_{j})\\}_{1\leq j\leq s}$ to form a tree $T$ (the
recursion ends when $X_{j}$ is a singleton). The one-to-many embedding $f$
simply defined as the union of the one-to-many embeddings $\\{f_{j}\\}_{0\leq
j\leq s}$. Note, however, that the clusters
$\widetilde{X}_{0},\widetilde{X}_{1},\dots,\widetilde{X}_{s}$ are not
disjoint. Therefore, in addition, for each cluster $\widetilde{X}_{j}$ the
petal-decomposition procedure will also provide us with sub-clusters
$\underline{X}_{j}\subseteq X_{j}\subseteq\widetilde{X}_{j}$ that will be used
to determine the chiefs (i.e. $\chi$ part) of the clan embedding.

1 if  _$|X|=1$_ then

2 return $G[X]$

3Let
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{j}\right\\}_{j=0}^{s},\left\\{(y_{j},x_{j})\right\\}_{j=1}^{s}\right)=\texttt{petal-
decomposition}(G[X],x_{0},t,\Delta)$

4 for  _each $j\in[0,\dots,s]$_ do

5 $(T_{j},f_{j},\chi_{j})=\texttt{hierarchical-petal-decomposition}$
$(G[\widetilde{X}_{j}],x_{j},t_{j},\Delta_{j})$

6

7for  _each $z\in X$_ do

8 Set $f(x)=\cup_{j=0}^{s}f_{j}(z)$

9 if  _$\exists j >0$ such that $z\in X_{j}$_ then

10 Let $j>0$ be the minimal index such that $z\in X_{j}$. Set
$\chi(z)=\chi_{j}(z)$

11 else

12 Set $\chi(z)=\chi_{0}(z)$

13

14Let $T$ be the tree formed by connecting $T_{0},\dots,T_{s}$ using the edges
$\\{\chi(y_{1}),\chi(x_{1})\\},\dots,\\{\chi(y_{s}),\chi(x_{s})\\}$

15 return $(T,f,\chi)$

Algorithm 1 $(T,f,\chi)=\texttt{hierarchical-petal-
decomposition}(G[X],x_{0},t,\Delta)$

Next, we describe the petal-decomposition procedure (see Algorithm 2).
Initially it sets $Y_{0}=X$, and for $j=1,2,\dots,s$, it carves out the petal
$\widetilde{X}_{j}$ from the graph induced on $Y_{j-1}$, and sets
$Y_{j}=Y_{j-1}\backslash\underline{X}_{j}$, where $\underline{X}_{j}$ is a
sub-petal of $\widetilde{X}_{j}$, consisting of all the vertices which are
padded by $\widetilde{X}_{j}$. The idea is that $Y_{j}$ is defined w.r.t. to a
smaller set than the petal itself; thus, by duplicating some vertices, we will
be able to guarantee that each vertex is padded somewhere. In order to control
the radius increase, the first petal might be carved using different
parameters (see [AN19] for details and explanation of this subtlety 121212One
may notice that in algorithm 2 of the petal-decomposition procedure, the
weight of some edges is changed by a factor of 2. This can happen at most once
for each copy of every edge throughout the hierarchical-petal-decomposition
execution, thus it may affect the padding parameter by a factor of at most 2.
This re-weighting is ignored here for simplicity. We again refer readers to
[AN19] for details and further explanation.). The definition of petal
guarantees that the radius $\Delta_{x_{0}}(Y_{j})$ is non-increasing, and when
at step $s$ it becomes at most $3\Delta/4$, define $X_{0}=Y_{s}$ and then the
petal-decomposition routine ends. In carving of the petal
$\widetilde{X}_{j}\subseteq Y_{j-1}$, the algorithm chooses an arbitrary
target $t_{j}\in Y_{j-1}$ (at distance at least $3\Delta/4$ from $x_{0}$) and
a range $[\mathrm{lo},\mathrm{hi}]$ of size
$\mathrm{hi}-\mathrm{lo}\in\\{\Delta/8,\Delta/4\\}$ which are passed to the
sub-routine create-petal.

1 Let $Y_{0}=X$

2 Set $j=1$

3

4if  _$d_{X}(x_{0},t)\geq\Delta/2$_ then

5 Let $(\underline{X}_{1},X_{1},\widetilde{X}_{1})=\texttt{create-
petal}(G[Y_{0}],[d_{X}(x_{0},t)-\Delta/2,d_{X}(x_{0},t)-\Delta/4],x_{0},t)$

6 $Y_{1}=Y_{0}\backslash\underline{X}_{1}$

7 Let $\\{x_{1},y_{1}\\}$ be the unique edge on the shortest path $P_{x_{0}t}$
from $x_{0}$ to $t$ in $Y_{0}$, where $x_{1}\in X_{1}$ and $y_{1}\in Y_{1}$

8 Set $t_{0}=y_{1}$, $t_{1}=t$; $j=2$

9else

10 set $t_{0}=t$

11

12while  _$Y_{j-1}\backslash B_{X}(x_{0},\frac{3}{4}\Delta)\neq\emptyset$_ do

13 Let $t_{j}\in Y_{j-1}$ be an arbitrary vertex satisfying
$d_{X}(x_{0},t_{j})>\frac{3}{4}\Delta$

14 Let $(\underline{X}_{j},X_{j},\widetilde{X}_{j})=\texttt{create-
petal}(G[Y_{j-1}],[0,\Delta/8],x_{0},t_{j})$

15 $Y_{j}=Y_{j-1}\backslash\underline{X}_{j}$

16 Let $\\{x_{j},y_{j}\\}$ be the unique edge on the shortest path
$P_{x_{j}t_{j}}$ from $x_{0}$ to $t_{j}$ in $Y_{j-1}$, where
$x_{j}\in\widetilde{X}_{j}$ and $y_{j}\in Y_{j}$

17 Consider $G_{j}=G[\widetilde{X}_{j}]$ the graph induced by
$\widetilde{X}_{j}$. For each edge $e\in P_{x_{j}t_{j}}(\widetilde{X}_{j})$,
set its weight to be $w(e)/2$

18 Let $j=j+1$

19

20

21Let $s=j-1$

22 Let $\underline{X}_{0}=X_{0}=\widetilde{X}_{0}=Y_{s}$

23 return
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{x_{j}}(\widetilde{X}_{j})\right\\}_{j=0}^{s},\left\\{(y_{j},x_{j})\right\\}_{j=1}^{s}\right)$

Algorithm 2
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{j}\right\\}_{j=0}^{s},\left\\{(y_{j},x_{j})\right\\}_{j=1}^{s}\right)=\texttt{petal-
decomposition}(G[X],x_{0},t,\Delta)$

Both hierarchical-petal-decomposition and petal-decomposition are essentially
the algorithms that appeared in [AN19]. The only technical difference is that
in [AN19] $\widetilde{X}_{j}=\underline{X}_{j}$ for every $j$ (as they created
actually spanning tree, while we are constructing a clan embedding). The more
important difference lies in the create-petal procedure, depicted in Algorithm
3. It carefully selects a radius $r\in[\mathrm{lo},\mathrm{hi}]$, which
determines the petal $\widetilde{X}_{j}$ together with a connecting edge
$(x_{j},y_{j})\in E$, where $x_{j}\in\widetilde{X}_{j}$ is the center of
$\widetilde{X}_{j}$ and $y_{j}\in Y_{j}$. It is important to note that the
target $t_{0}\in X_{0}$ of the central cluster $X_{0}$ is determined during
the creation of the first petal $X_{1}$. The petals are created using an
alternative metric on the graph, known as the cone-metric:

######  Definition 8 (Cone-metric).

Given a graph $G=(V,E)$, a subset $X\subseteq V$ and points $x,y\in X$, define
the cone-metric $\rho=\rho(X,x,y):X^{2}\to\mathbb{R}^{+}$ as
$\rho(u,v)=\left|\left(d_{X}(x,u)-d_{X}(y,u)\right)-\left(d_{X}(x,v)-d_{X}(y,v)\right)\right|$.

The cone-metric is in fact a pseudo-metric, i.e., distances between distinct
points are allowed to be 0. The ball $B_{(X,\rho)}(y,r)$ in the cone-metric
$\rho=\rho(X,x,y)$, contains all vertices $u$ whose shortest path to $x$ is
increased (additively) by at most $r$ if forced to go through $y$. In the
create-petal algorithm, while working in a subgraph $G[Y]$ with two specified
vertices: a center $x_{0}$ and a target $t$, we define
$W_{r}\left(Y,x_{0},t\right)=\bigcup_{p\in P_{x_{0}t}:\ d_{Y}(p,t)\leq
r}B_{(Y,\rho(Y,x_{0},p))}(p,\frac{r-d_{Y}(p,t)}{2})$ which is union of balls
in the cone-metric, where any vertex $p$ in the shortest path from $x_{0}$ to
$t$ of distance at most $r$ from $t$ is a center of a ball with radius
$\frac{r-d_{Y}(p,t)}{2}$. See Figure 3 for an illustration. The parameters
$(Y,x_{0},t)$ are usually clear from the context and hence omitted. The
following fact from [AN19] demonstrates that petals are similar to balls.

Figure 3: On the left, we illustrate the ball $B_{(X,\rho)}(t,r)$ in the cone-
metric $\rho=\rho(X,x,t)$ containing all vertices $u$ whose shortest path to
$x$ is increased (additively) by at most $r$ if forced to go through $t$. The
red vertex $z$ joins $B_{(X,\rho)}(t,r)$ as $d_{X}(z,t)+d_{X}(t,x)\leq
d_{X}(z,x)+r$. The blue point $q$ on the path $P_{t,x}$ at distance
$\frac{r}{2}$ from $t$ is the last point on $P_{t,x}$ to join
$B_{(X,\rho)}(t,r)$.
On the right, we illustrate the petal $W_{r}\left(X,x,t\right)=\bigcup_{p\in
P_{xt}:\ d_{Y}(p,t)\leq r}B_{(Y,\rho(X,x,p))}(p,\frac{r-d_{X}(p,t)}{2})$. In
the illustration, the point $p_{i}$ is at distance $\frac{i}{4}r$ from $t$,
and is the center of a ball of radius $\frac{4-i}{8}r$ in the respective cone
metric.

######  Fact 1 ([AN19]).

For every $y\in W_{r}\left(Y,x_{0},t\right)$ and $l\geq 0$,
$B_{G[Y]}(y,l)\subseteq W_{r+4l}\left(Y,x_{0},t\right)$.

Note that 1 implies that $W_{r}$ is monotone in $r$, i.e., for $r\leq
r^{\prime}$, it holds that $W_{r}\subseteq W_{r^{\prime}}$.

For each $j$, the clusters $\underline{X}_{j},X_{j},\widetilde{X}_{j}$
returned by the create-petal procedure executed on
$(G[Y_{j-1}],[\mathrm{lo},\mathrm{hi}],x_{0},t_{j})$ will all be petals of the
form $W_{r}(Y_{j-1},x_{0},t_{j})$ for $r\in[\mathrm{lo},\mathrm{hi}]$.
Specifically, we will chose some
$r_{1},r_{2},r_{3}\in[\mathrm{lo},\mathrm{hi}]$ such that
$\underline{X}_{j}=W_{r_{1}}(Y_{j-1},x_{0},t_{j})$,
$X_{j}=W_{r_{2}}(Y_{j-1},x_{0},t_{j})$ and
$\widetilde{X}_{j}=W_{r_{3}}(Y_{j-1},x_{0},t_{j})$ while
$r_{2}-r_{1}=r_{3}-r_{2}=\Theta(\frac{\mathrm{hi}-\mathrm{lo}}{k\log\log\mu(Y_{j-1})})$.

The following facts were proven in [AN19] regarding the petal-decomposition
procedure. They hold in our version of the algorithm using exactly the same
proofs.

######  Fact 2 ([AN19]).

Consider the petal-decomposition procedure executed on $X$ with center
$x_{0}$, target $t$ and radius $\Delta$. It creates clusters
$(\underline{X_{0}},X_{0},\widetilde{X_{0}}),(\underline{X_{1}},X_{1},\widetilde{X_{1}}),\dots,(\underline{X_{s}},X_{s},\widetilde{X_{s}})$.
During the process, we had temporary metrics $Y_{0}=X$, and
$Y_{j}=Y_{j-1}\backslash\underline{X_{j}}$. For $j\geq 1$ the cluster
$\widetilde{X}_{j}$ had center $x_{j}$ connected to $y_{j}\in Y_{j}$ and
target $t_{j}\in\widetilde{X}_{j}$. Throughout the execution, the following
hold:

  1. 1.

For every $j$ and $z\in Y_{j}$, $P_{z,x_{0}}(X)\subseteq G[Y_{j}]$. In
particular, the radius of the $Y_{j}$’s is monotonically non-increasing:
$\Delta_{x_{0}}(Y_{0})\geq\Delta_{x_{0}}(Y_{1})\geq\dots\geq\Delta_{x_{0}}(Y_{s})$.
In particular $X_{0}$ is a connected cluster with radius at most $3\Delta/4$.

  2. 2.

For each $j\geq 0$, $\widetilde{X}_{j}$ is a connected cluster with center
$x_{j}$, target $t_{j}$ such that $\Delta_{x_{j}}(X_{j})\leq 3\Delta/4$. In
particular, the entire shortest path from $x_{j}$ to $t_{j}$ (in $Y_{j-1}$) is
in $\widetilde{X}_{j}$.

  3. 3.

If a special first cluster is created, then $y_{1}\in X_{0}$ and
$P_{x_{0},t}(X)\subseteq G[X_{0}\cup X_{1}]$. If no special first cluster is
created, then $P_{x_{0},t}(X)\subseteq G[X_{0}]$.

Next, we cite the relevant properties regarding the hierarchical-petal-
decomposition procedure. The proofs follow almost the same lines as [AN19],
with slight and natural adaptations due to the embedding being a clan
embedding with duplicate copies for some vertices. In any case, no new ideas
are required and we will skip the proof.

######  Fact 3 ([AN19]).

Consider the hierarchical-petal-decomposition procedure executed on $X$ with
center $x_{0}$, target $t$ and radius $\Delta$. The following properties hold:

  1. 1.

The algorithm returns a spanning clan embedding into a tree $T$.

  2. 2.

The tree $T$ has radius at most $4\Delta_{x_{0}}(X)$. That is

$\Delta_{x_{0}}(T)\leq 4\Delta_{x_{0}}(X)\leavevmode\nobreak\ .$

Note that it follows from 3, that the distance between every pair of vertices
in the tree $T$ is at most $8\Delta_{x_{0}}(X)$.

We will need the following observation. Roughly speaking, it says that when
the petal-decomposition algorithm is carving out
$(\underline{X}_{j+1},X_{j+1},\widetilde{X}_{j+1})$, it is oblivious to the
past petals, edges and targets – it only cares about $Y_{j}$ and the original
diameter $\Delta$.

######  Observation 1.

Assume that petal-decomposition on input
$(G\left[X\right],x_{0},t,\Delta_{x_{0}}(X))$ returns as output
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{j}\right\\}_{j\in\\{0,\dots,s\\}},\left\\{(y_{j},x_{j})\right\\}_{j\in\\{1,\dots,s\\}}\right)$.
Then running petal-decomposition on input
$(G\left[Y_{l}\right],x_{0},t_{0},\Delta_{x_{0}}(X))$ will output
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{j}\right\\}_{j\in\\{0,l+1,\dots,s\\}},\left\\{(y_{j},x_{j})\right\\}_{j\in\\{l+1,\dots,s\\}}\right)$.

###  4.2 Choosing a Radius

Fix some $1\leq j\leq s$, and consider carving the petal
$(\underline{X}_{j},X_{j},\widetilde{X}_{j})$ from the graph induced on
$Y=Y_{j-1}$. Our choice of radius bears similarities to the one in [ACE+20].
The properties of the petal decomposition described above (in Section 4.1),
together with 2 and 3, hold for any radius picked from a given interval. We
will now describe the method to select a radius that suits our needs. The
petal-decomposition algorithm provides an interval $[\mathrm{lo},\mathrm{hi}]$
of size at least $\Delta/8$, and for each $r\in[\mathrm{lo},\mathrm{hi}]$ let
$W_{r}(Y,x_{0},t)\subseteq Y$ denote the petal of radius $r$ (usually we will
omit $(Y,x_{0},t)$.).

Our algorithm will return three clusters: $\underline{X}_{j}\subseteq
X_{j}\subseteq\widetilde{X}_{j}$ which will correspond to three petals
$W_{r-\frac{R}{4Lk}}\subseteq W_{r}\subseteq W_{r+\frac{R}{4Lk}}$
respectively, where
$\frac{R}{4Lk}=\Theta(\frac{\mathrm{hi}-\mathrm{lo}}{k\log\log\mu(Y)})=\Theta(\frac{\Delta}{k\log\log\mu(Y)})$.
The algorithm will be executed recursively on $\widetilde{X}_{j}$, while
$\underline{X}_{j}$ will be removed from $Y$. The cluster $X_{j}$ will only be
used in order to define $\chi$ (during the hierarchical-petal-decomposition
procedure). 1 implies that the vertices in $X_{j}$ are padded by
$\widetilde{X}_{j}$, while the vertices in $Y\backslash X_{j}$ are padded by
$Y\backslash\underline{X}_{j}$. If a pair of vertices $u,v$ do not belong to
the same cluster (e.g. $u\in\underline{X}_{j}$ and $v\notin\widetilde{X}_{j}$)
then $d_{Y}(u,v)=\Omega(\frac{\Delta}{k\log\log\mu(Y)})$. By 3, the diameter
of the final tree will be $O(\Delta)$. In particular, the distance in the
embedded tree between every copy of $u$ and $v$ will be bounded by
$O(\Delta)=O(k\log\log\mu(Y))d_{Y}(u,v)$. Note that only the vertices in
$\widetilde{X}_{j}\backslash\underline{X}_{j}$ are duplicated. Thus, our goal
is to choose a radius $r$ such that the measure of the duplicated vertices
would be small.

Our algorithm to select a radius is based on region growing techniques as in
[ACE+20], which is more involved than the region growing in Theorem 1. In the
petal decomposition framework, we cannot pick as the center a vertex
maximizing the ”small ball” (as the target $t_{j}$ must be at distance
$\frac{3}{4}$ from $x_{0}$). We first choose an appropriate range that mimics
that choice (see algorithm 3 in Algorithm 3) — this is the reason for the
extra factor of $\log\log\mu(Y)$. The basic idea in region growing is to
charge the measure of the duplicated vertices (i.e.
$\widetilde{X}_{j}\backslash\underline{X}_{j}$), to all the vertices in the
cluster $\widetilde{X}_{j}$. In order to avoid a range in
$[\mathrm{lo},\mathrm{hi}]$ that contains more than half of the measure, we
will cut either in $[\mathrm{lo},\mathrm{mid}]$ or in
$[\mathrm{mid},\mathrm{hi}]$ where $\mathrm{mid}=(\mathrm{hi}+\mathrm{lo})/2$.
Specifically, in the case where $W_{\mathrm{mid}}$ has measure at least
$\mu(Y)/2$, we ”cut backward” in the regime $[\mathrm{mid},\mathrm{hi}]$, and
charge the measure of duplicated vertices to the remaining graph $Y_{j}$,
rather than to $\widetilde{X}_{j}$.

1 $L=\lceil 1+\log\log\mu(Y)\rceil$

2 $R=\mathrm{hi}-\mathrm{lo}$;
$\mathrm{mid}=(\mathrm{lo}+\mathrm{hi})/2=\mathrm{lo}+R/2$

3 For every $r$, denote $W_{r}=W_{r}(Y,x_{0},t)$, $w_{r}=\mu(W_{r})$

4 if  _$w_{\mathrm{mid}}\leq\frac{\mu(Y)}{2}$_ then

Choose $\left[a,b\right]\subseteq\left[\mathrm{lo},\mathrm{mid}\right]$ such
that $b-a=\frac{R}{2L}$ and $w_{a}\geq w_{b}^{2}/\mu(Y)$

// see Lemma 8

5

Pick $r\in\left[a+\frac{b-a}{2k},b-\frac{b-a}{2k}\right]$ such that
$w_{r+\frac{b-a}{2k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{\frac{1}{k}}$

// see Lemma 9

6

7else

8 For every $r\in[\mathrm{lo},\mathrm{hi}]$, denote $q_{r}=\mu(Y\backslash
W_{r})$

Choose $\left[b,a\right]\subseteq\left[\mathrm{mid},\mathrm{hi}\right]$ such
that $a-b=\frac{R}{2L}$ and $q_{a}\geq q_{b}^{2}/\mu(Y)$

// see Lemma 10

9

Pick $r\in\left[b+\frac{b-a}{2k},a-\frac{b-a}{2k}\right]$ such that
$q_{r-\frac{a-b}{2k}}\leq
q_{r+\frac{a-b}{2k}}\cdot\left(\frac{q_{b}}{q_{a}}\right)^{1/k}$

// see Lemma 11

10

11return $(W_{r-\frac{R}{4Lk}},W_{r},W_{r+\frac{R}{4Lk}})$

Algorithm 3 $(\underline{X},X,\widetilde{X})=\texttt{create-
petal}(G[Y],\mu,[\mathrm{lo},\mathrm{hi}],x_{0},t)$

###  4.3 Proof of Lemma 5: the distributional case

Let $u,v\in V$ be a pair of vertices, let $(f,\chi)$ be the spanning clan
embedding into a tree $T$ returned by calling hierarchical-petal-decomposition
on $(G[V],z,z,\Delta_{z}(V))$ for arbitrary $z\in V$.

######  Lemma 6.

The clan embedding $(f,\chi)$ has distortion $O(\rho)=O(k\log\log\mu(V))$.

###### Proof.

The proof is by induction on the radius $\Delta$ of the graph (w.r.t. the
center). The basic case is where the graph is a singleton and $\Delta=0$ is
trivial. For the general case, consider a pair of vertices $u,v$. Let
$\left(\left\\{\underline{X}_{j},X_{j},\widetilde{X}_{j},x_{j},t_{j},\Delta_{j}\right\\}_{j=0}^{s},\left\\{(y_{j},x_{j})\right\\}_{j=1}^{s}\right)$
be the output of the call to the petal-decomposition procedure on $X,x_{0}$.
For each $j\geq 1$, let $Y_{j-1}$ be the graph held during the $j$’th stage of
the algorithm. Note that $Y_{s}=X_{0}$. Then we created the petals
$(\underline{X}_{j},X_{j},\widetilde{X}_{j})=(W_{r_{j}-\frac{R}{4Lk}},W_{r_{j}},W_{r_{j}+\frac{R}{4Lk}})$,
and $Y_{j}=Y_{j-1}\backslash\underline{X}_{j}$, where $L=\lceil
1+\log\log\mu(Y_{j})\rceil$, and $R\geq\frac{\Delta}{8}$. Set
$\rho=128\left\lceil 1+\log\log\mu(V)\right\rceil\cdot k=O(k\log\log\mu(V))$.
Note that for every execution of the create-petal procedure at this stage, it
holds that $\frac{\Delta}{\rho}\leq\frac{1}{4}\cdot\frac{R}{4Lk}$.

First, consider the case where $d_{G}(u,v)\geq\frac{\Delta}{\rho}$. By 3, the
distance between any pair of vertices in $T$ is $O(\Delta)$. In particular

$\min_{v^{\prime}\in f(v)}d_{T}(v^{\prime},\chi(u))=O(\Delta)=O(\rho)\cdot
d_{G}(u,v)\leavevmode\nobreak\ .$

Otherwise, $d_{G}(u,v)<\frac{\Delta}{\rho}$. Let
$B=B_{X}(u,\frac{\Delta}{\rho})$. For ease of notation, set
$\underline{X}_{s+1}=X_{s+1}=\widetilde{X}_{s+1}=X_{0}=Y_{s}$. Let
$j_{u}\in[1,s+1]$ be the minimal index such that $u\in X_{j}$. We argue that
$B\subseteq Y_{j_{u}-1}$. Assume otherwise, and let $j\in[1,j_{u}-1]$ be the
minimal index such that $B\nsubseteq Y_{j}$. Thus, there is a vertex
$u^{\prime}\in B\cap\underline{X}_{j}\subseteq W_{r_{j}-\frac{R}{4Lk}}$, while
by the minimality of $j$, it holds that $B\subseteq Y_{j-1}$. Using 1, it
follows that

$u\in B_{Y_{j-1}}(u^{\prime},\frac{\Delta}{\rho})\subseteq
W_{r_{j}-\frac{R}{4Lk}+4\cdot\frac{\Delta}{\rho}}\subseteq
W_{r_{j}}=X_{j}\leavevmode\nobreak\ ,$

a contradiction to the minimality of $j_{u}$.

Next, we argue that $B\subseteq\widetilde{X}_{j_{u}}$. If $j_{u}=s+1$, then we
have $B\subseteq Y_{s}=X_{0}=\widetilde{X}_{s+1}$ and done. Otherwise, as
$u\in X_{j_{u}}=W_{r_{j_{u}}}$, using 1 again we obtain

$B=B_{X}(u,\frac{\Delta}{\rho})=B_{Y_{j_{u}-1}}(u,\frac{\Delta}{\rho})\subseteq
W_{r_{j_{u}}+4\cdot\frac{\Delta}{\rho}}\subseteq
W_{r_{j_{u}}+\frac{R}{4Lk}}=\widetilde{X}_{j_{u}}\leavevmode\nobreak\ .$

In the hierarchical-petal-decomposition algorithm, we create a clan embedding
$(f_{j_{u}},\chi_{j_{u}})$ of $\widetilde{X}_{j_{u}}$ into a tree $T_{j_{u}}$.
The tree $T_{j_{u}}$ is incorporated into a global tree $T$, where
$f(u)=\cup_{j}f_{j}(u)$, $f(v)=\cup_{j}f_{j}(v)$, and
$\chi(u)=\chi_{j_{u}}(u)$ by the definition of $j_{u}$. As
$d_{G}(u,v)<\frac{\Delta}{\rho}$, it holds that $v\in B$. In particular, the
shortest path from $v$ to $u$ in $G$ belongs to $B$, thus
$d_{G[X_{j_{u}}]}(u,v)=d_{G}(u,v)$. By 2, the radius of $X_{j_{u}}$ is at most
$\frac{3}{4}\Delta$; hence, using the induction hypothesis, we conclude that:

$\min_{v^{\prime}\in f(v)}d_{T}(v^{\prime},\chi(u))\leq\min_{v^{\prime}\in
f_{j_{u}}(v)}d_{T_{j_{u}}}(v^{\prime},\chi_{j_{u}}(u))=O(\rho)\cdot
d_{G[X_{j_{u}}]}(u,v)=O(\rho)\cdot d_{G}(u,v)\leavevmode\nobreak\ .$

∎

######  Lemma 7.

$\mathbb{E}_{v\sim\mu}[|f(v)|]\leq\mu(V)^{1+1/k}$.

###### Proof.

We prove by induction on $|X|$ and $\Delta$ that the one-to-many embedding $f$
constructed using the hierarchical-petal-decomposition algorithm w.r.t. any
$(\geq 1)$-measure $\mu$ fulfills
$\mathbb{E}_{v\sim\mu}[|f(v)|]\leq\mu(X)^{1+1/k}$. The base case where $X$ is
a singleton is trivial. For the inductive step, assume we call petal-
decomposition on $(G[X],x_{0},t,\Delta)$ with $\Delta\geq\Delta_{x_{0}}(X)$
and measure $\mu$.

Assume that the petal-decomposition algorithm does a non-trivial clustering of
$X$ to $\widetilde{X}_{0},\widetilde{X}_{1},\dots,\widetilde{X}_{s}$. (If it
is the case that all vertices are sufficiently close to $x_{0}$, then no petal
will be created, and the hierarchical-petal-decomposition will simply recurse
on $(G[X],x_{0},t,\Delta_{x_{0}}(X))$, so we can ignore this case.) Let
$\widetilde{X}_{1}=W_{r+\frac{R}{4Lk}}$ be the first petal created by the
petal-decomposition algorithm, and $Y_{1}=X\backslash\underline{X}_{1}$, where
$\underline{X}_{1}=W_{r-\frac{R}{4Lk}}$. Denote by $\mu_{\widetilde{X}_{j}}$
the measure $\mu$ restricted to $\widetilde{X}_{j}$, and by
$f_{\widetilde{X}_{j}}$ the one-to-many embedding our algorithm constructs for
$\widetilde{X}_{j}$.

By 1, we can consider the remaining execution of petal-decomposition on
$Y_{1}$ as a new recursive call of petal-decomposition with input
$(G[Y_{1}],x_{0},t_{0},\Delta)$. In particular, the recursive calls on
$\widetilde{X}_{0},\widetilde{X}_{2},\dots,\widetilde{X}_{s}$ are completely
independent from $\widetilde{X}_{1}$. Denote
$f_{Y_{1}}=\cup_{j=0,2,\dots,s}f_{\widetilde{X}_{j}}$, and by $\mu_{{Y}_{1}}$
the measure $\mu$ restricted to $Y_{1}$. Since
$|\widetilde{X}_{1}|,|Y_{1}|<|X|$, the induction hypothesis implies that
$\mathbb{E}_{v\sim\mu_{\widetilde{X}_{1}}}[|f_{\widetilde{X}_{1}}(v)|]\leq\mu_{\widetilde{X}_{1}}(\widetilde{X}_{1})^{1+\frac{1}{k}}=\mu(\widetilde{X}_{1})^{1+\frac{1}{k}}$
and
$\mathbb{E}_{v\sim\mu_{Y_{1}}}[|f_{Y_{1}}(v)|]\leq\mu_{Y_{1}}(Y_{1})^{1+\frac{1}{k}}=\mu(Y_{1})^{1+\frac{1}{k}}$.
Note that by our construction,

$\mathbb{E}_{v\sim\mu}[|f(v)|]=\sum_{j=0}^{s}\mathbb{E}_{v\sim\mu_{\widetilde{X}_{j}}}[|f_{j}(v)|]=\mathbb{E}_{v\sim\mu_{\widetilde{X}_{1}}}[|f_{1}(v)|]+\mathbb{E}_{v\sim\mu_{Y_{1}}}[|f_{Y_{1}}(v)|]\leavevmode\nobreak\
.$

The rest of the proof is by case analysis according to the choice of radii in
Algorithm 3. Recall that $w_{r^{\prime}}=\mu(W_{r^{\prime}})$ and
$q_{r^{\prime}}=\mu(Y\setminus W_{r^{\prime}})=\mu(X\setminus W_{r^{\prime}})$
for every parameter $r^{\prime}$.

  1. 1.

Case 1: $w_{\mathrm{mid}}\leq\mu(X)/2$. In this case, we pick
$a,b\in[\mathrm{lo},\mathrm{hi}]$ where $b-a=R/(2L)$, and
$r\in\left[a+\frac{b-a}{2k},b-\frac{b-a}{2k}\right]$ such that

$w_{a}>w_{b}^{2}/\mu(X)\qquad\qquad\mbox{and}\qquad\qquad
w_{r+\frac{b-a}{2k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{1/k}\leavevmode\nobreak\
.$

Here $\widetilde{X}_{1}=W_{r+\frac{b-a}{2k}}$, while
$Y_{1}=X\backslash\underline{X}_{1}=X\backslash W_{r-\frac{b-a}{2k}}$. Using
these two inequalities, we have that

$\mu(\widetilde{X}_{1})^{1+\frac{1}{k}}=w_{r+\frac{b-a}{2k}}\cdot
w_{r+\frac{b-a}{2k}}^{\frac{1}{k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{\frac{1}{k}}\cdot
w_{r+\frac{b-a}{2k}}^{\frac{1}{k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\left(\frac{\mu(X)}{w_{b}}\right)^{\frac{1}{k}}\cdot
w_{r+\frac{b-a}{2k}}^{\frac{1}{k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\mu(X)^{\frac{1}{k}}\leavevmode\nobreak\ ,$

where we used the fact that $r+\frac{b-a}{2k}\leq b$ (and that $w_{r}$ is
monotone). Using the induction hypothesis, we conclude that

$\displaystyle\mathbb{E}_{x\sim\mu}[|f(x)|]$
$\displaystyle=\mathbb{E}_{x\sim\mu_{\widetilde{X}_{1}}}[|f_{\widetilde{X}_{1}}(x)|]+\mathbb{E}_{x\sim\mu_{Y_{1}}}[|f_{Y_{1}}(x)|]$
$\displaystyle\leq\mu(\widetilde{X}_{1})^{1+\frac{1}{k}}+\mu(Y_{1})^{1+\frac{1}{k}}$
$\displaystyle\leq
w_{r-\frac{b-a}{2k}}\cdot\mu(X)^{\frac{1}{k}}+\mu(Y_{1})\cdot\mu(X)^{\frac{1}{k}}$
$\displaystyle=\left(\mu(W_{r-\frac{b-a}{2k}})+\mu(X\backslash
W_{r-\frac{b-a}{2k}})\right)\cdot\mu(X)^{\frac{1}{k}}=\mu(X)^{1+\frac{1}{k}}\leavevmode\nobreak\
,$

where the second inequality is because $\mu(Y_{1})\leq\mu(X)$.

  2. 2.

Case 2: $w_{\mathrm{mid}}>\mu(X)/2$. This case is completely symmetric.
Denoting $q_{r}=\mu(X\setminus W_{r})$, we picked
$b,a\in[\mathrm{lo},\mathrm{hi}]$ so that $a-b=R/(2L)$ and
$r\in\left[b+\frac{b-a}{2k},a-\frac{b-a}{2k}\right]$ such that

$q_{a}\geq q_{b}^{2}/\mu(X)\qquad\qquad\mbox{and}\qquad\qquad
q_{r-\frac{a-b}{2k}}\leq
q_{r+\frac{a-b}{2k}}\cdot\left(\frac{q_{b}}{q_{a}}\right)^{1/k}\leavevmode\nobreak\
,$

Here $\widetilde{X}_{1}=W_{r+\frac{b-a}{2k}}$, while $Y_{1}=X\backslash
W_{r-\frac{b-a}{2k}}$. Note that $\mu(Y_{1})=q_{r-\frac{a-b}{2k}}$ while
$\mu(\widetilde{X}_{1})=\mu(X)-q_{r+\frac{a-b}{2k}}$. Using this two
inequalities we have that

$\mu(Y_{1})^{1+\frac{1}{k}}=q_{r-\frac{b-a}{2k}}\cdot
q_{r-\frac{b-a}{2k}}^{\frac{1}{k}}\leq
q_{r+\frac{b-a}{2k}}\cdot\left(\frac{q_{b}}{q_{a}}\right)^{\frac{1}{k}}\cdot
q_{r-\frac{b-a}{2k}}^{\frac{1}{k}}\leq
q_{r+\frac{b-a}{2k}}\cdot\left(\frac{\mu(X)}{q_{b}}\right)^{\frac{1}{k}}\cdot
q_{r-\frac{b-a}{2k}}^{\frac{1}{k}}\leq
q_{r+\frac{b-a}{2k}}\cdot\mu(X)^{\frac{1}{k}}$

where we used the fact that $b\leq r-\frac{b-a}{2k}$. Following previous
calculations, we conclude that:

$\displaystyle\mathbb{E}_{x\sim\mu}[|f(x)|]$
$\displaystyle\leq\mu(\widetilde{X}_{1})^{1+\frac{1}{k}}+\mu(Y_{1})^{1+\frac{1}{k}}$
$\displaystyle\leq\mu(\widetilde{X}_{1})\mu(X)^{\frac{1}{k}}+q_{r+\frac{b-a}{2k}}\cdot\mu(X)^{\frac{1}{k}}$
$\displaystyle=\left(\mu(W_{r+\frac{a-b}{2k}})+\mu(X\backslash
W_{r+\frac{a-b}{2k}})\right)\cdot\mu(X)^{\frac{1}{k}}=\mu(X)^{1+\frac{1}{k}}\leavevmode\nobreak\
.$

∎

Lemma 5 follows by the combination of Lemma 6 and Lemma 7.

###  4.4 Missing proofs from the create-petal procedure (Algorithm 3)

In this section we prove that the choices made in the create-petal procedure
are all legal. In all lemmas in this section, we shall use the notation in
Algorithm 3.

######  Lemma 8.

If $w_{\mathrm{mid}}\leq\mu(Y)/2$ then there is
$\left[a,b\right]\subseteq\left[\mathrm{lo},\mathrm{mid}\right]$ such that
$b-a=\frac{R}{2L}$ and $w_{a}\geq w_{b}^{2}/\mu(Y)$.

###### Proof.

Seeking contradiction, assume that for every such $a,b$ with
$b-a=\frac{R}{2L}$ it holds that $w_{b}>\sqrt{\mu(Y)\cdot w_{a}}$. Applying
this on $b=\mathrm{mid}-\frac{iR}{2L}$ and $a=\mathrm{mid}-\frac{(i+1)R}{2L}$
for every $i=0,1,\dots,L-2$, we have that

$w_{\mathrm{mid}}>\mu(Y)^{1/2}\cdot
w_{\mathrm{mid}-\frac{R}{2L}}^{1/2}>\dots>\mu(Y)^{1-2^{-(L-1)}}\cdot
w_{\mathrm{mid}-\frac{(L-1)R}{2L}}^{2^{-(L-1)}}\geq\mu(Y)\cdot 2^{-1}\cdot
w_{\mathrm{lo}}^{2^{-(L-1)}}\geq\frac{\mu(Y)}{2}\leavevmode\nobreak\ ,$

where we used that $\log\log\mu(Y)\leq L-1$ and
$\mathrm{mid}=\mathrm{lo}+R/2$. In the last inequality, we also used that
$W_{\mathrm{lo}}$ contains at least one vertex, thus $w_{\mathrm{lo}}\geq 1$.
The contradiction follows. ∎

######  Lemma 9.

There is $r\in\left[a+\frac{b-a}{2k},b-\frac{b-a}{2k}\right]$ such that
$w_{r+\frac{b-a}{2k}}\leq
w_{r-\frac{b-a}{2k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{\frac{1}{k}}$.

###### Proof.

Seeking contradiction, assume there is no such choice of $r$. Then applying
the inequality for $r=b-(i+1/2)\cdot\frac{b-a}{k}$ for $i=0,1,\dots,k-1$ we
get

$w_{b}>w_{b-\frac{b-a}{k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{1/k}>\cdots>w_{b-k\cdot\frac{b-a}{k}}\cdot\left(\frac{w_{b}}{w_{a}}\right)^{k/k}=w_{a}\cdot\frac{w_{b}}{w_{a}}=w_{b}\leavevmode\nobreak\
,$

a contradiction. ∎

The following two lemmas are symmetric to the two lemmas above.

######  Lemma 10.

If $w_{\mathrm{mid}}>\frac{\mu(Y)}{2}$ (implies
$q_{\mathrm{mid}}\leq\frac{\mu(Y)}{2}$), then there is
$\left[b,a\right]\subseteq\left[\mathrm{mid},\mathrm{hi}\right]$ such that
$a-b=\frac{R}{2L}$ and $q_{a}\geq q_{b}^{2}/\mu(Y)$.

######  Lemma 11.

There is $r\in\left[b+\frac{b-a}{2k},a-\frac{b-a}{2k}\right]$ such that
$q_{r-\frac{a-b}{2k}}\leq
q_{r+\frac{a-b}{2k}}\cdot\left(\frac{q_{b}}{q_{a}}\right)^{1/k}$.

###  4.5 Grand finale: proof of Theorem 3

The proof of Theorem 3 using Lemma 5 follows the same lines as the proof of
Theorem 1 from Lemma 2. First we transform the language of $(\geq 1)$-measure
to that of probability measure.

######  Lemma 12.

Given an $n$-point weighted graph $G=(V,E,w)$ and probability measure
$\mu:V\rightarrow\mathbb{R}_{\geq 0}$, we can construct the two following
spanning clan embeddings $(f,\chi)$ into a tree:

  1. 1.

For integer $k\geq 1$, multiplicative distortion $O(k\log\log n)$ such that
$\mathbb{E}_{x\sim\mu}[|f(x)|]\leq O(n^{\frac{1}{k}})$.

  2. 2.

For $\epsilon\in(0,1]$, multiplicative distortion $O(\frac{\log n\log\log
n}{\epsilon})$ such that $\mathbb{E}_{x\sim\mu}[|f(x)|]\leq 1+\epsilon$.

The proof of Lemma 12 is exactly identical to that of Lemma 3 and we will skip
it. The only subtlety to note is the $(\geq 1)$-measure $\widetilde{\mu}_{\geq
1}$ constructed during the proof of Lemma 3 fulfills $\widetilde{\mu}_{\geq
1}(V)=2n$, and thus the multiplicative distortion guarantee from Lemma 5 will
be $O(k\log\log n)$. Theorem 3 now follows from the minimax theorem (in the
exact same way as the proof of Theorem 1).

##  5 Lower Bound for Clan Embeddings into Trees

This section is devoted to proving Theorem 2 that we restate below. See 2

The girth of an unweighted graph $G$ is the length of the shortest cycle in
$G$. The Erdős’ girth conjecture states that for any $g$ and $n$, there exists
an $n$-vertex graph with girth $g$ and $\Omega(n^{1+\frac{2}{g-2}})$ edges.
The conjecture is known to holds for $g=4,6,8,12$ (see [Ben66, Wen91]).
However, the best known lower bound for general $k$ is due to Lazebnik et al.
[LUW95].

######  Theorem 10 ([LUW95]).

For every even $g$, and $n$, there exists an unweighted graph with girth $g$
and $\Omega(n^{1+\frac{4}{3}\cdot\frac{1}{g-2}})$ edges.

From the upper bound perspective, the (generalized) Moore’s bound [AHL02,
BR10] states that every $n$ vertex graph with girth $g$ has at most
$n^{1+\frac{2}{g-2}}$ edges for $g\leq 2\log n$, and at most
$n\left(1+(1+o(1))\frac{\ln(m-n+1)}{g}\right)$ edges for larger $g$; here $m$
is the number of edges.

We will be able to use Theorem 10 to prove the second assertion in Theorem 2.
That is, any clan embedding into a tree with distortion $O(k)$ must have
$\sum_{x\in X}|f(x)|\geq\Omega(n^{1+\frac{1}{k}})$. However, the first
assertion requires a much tighter lower bound of $(1+\epsilon)n$ on the number
of edges. Therefore, the asymptotic nature of Theorem 10 is unfortunately not
strong enough for our needs. We begin by showing that for large enough $n$ and
$\epsilon\in(0,1)$, there exists an $n$-vertex graph with $(1+\epsilon)n$
edges and girth $\Omega(\frac{\log n}{\epsilon})$. We are not aware of this
very basic fact to previously appear in the literature. Note that Lemma 13
matches Moore’s upper bound (up to a constant dependency on the girth $g$).

######  Lemma 13.

For every fixed $\epsilon\in(0,1)$ and large enough $n$, there exists a graph
with at least $(1+\epsilon)n$ edges and girth $\Omega(\frac{\log
n}{\epsilon})$.

######  Remark 2 (Ultra sparse spanners).

Given a graph $G=(V,E,w)$, a $t$-spanner is a subgraph $H$ of $G$ such that
for every pair of vertices $u,v\in V$, $d_{H}(u,v)\leq t\cdot d_{G}(u,v)$. For
every fixed $\epsilon\in(0,1)$, Elkin and Neiman [EN19] constructed ultra-
sparse spanners with $(1+\epsilon)n$ edges and stretch $O(\frac{\log
n}{\epsilon})$. Even though they noted that the sparsity of their spanner
matches the Moore’s bound, it remained open whether one can construct better
spanners. As the only $(g-2)$-spanner of a graph with girth $g$ is the graph
itself, Lemma 13 implies that the ultra sparse spanner from [EN19] is tight
(up to a constant in the stretch).

For the case of girth $\Omega(\log n)$, the first step is to replace the
asymptotic notation in the lower bound on the number of edges from Theorem 10
with explicit bound.

######  Claim 2.

For every $n\in N$, there exist an $n$-vertex graph with $2n$ edges and girth
$\Omega(\log n)$.

###### Proof.

Set $p=\frac{4n}{{n\choose 2}}=\frac{8}{n-1}$. Consider a graph $G=(V,E)$
sampled according to $G(n,p)$ (that is, each edge sampled to $G$ i.i.d. with
probability $p$.). It holds that $\mathbb{E}[|E|]={n\choose 2}\cdot p=4n$. By
Chernoff bound,

$\Pr\left[|E|<3n\right]\leq
e^{-\frac{1}{32}\mathbb{E}[E]}=e^{-\frac{n}{8}}\leavevmode\nobreak\ .$

On the other hand, for $t\geq 3$, denote by $C_{t}$ the set of cycles of
length exactly $t$. Then,

$\mathbb{E}\left[|C_{t}|\right]\leq n(n-1)\cdots(n-t+1)\cdot
p^{t}=\frac{n(n-1)\cdots(n-t+1)}{(n-1)^{t}}\cdot
4^{t}<4^{t}\leavevmode\nobreak\ .$

Denote by $\mathcal{C}$ the set of all cycles of length smaller than
$\frac{1}{3}\log n$. Then

$\mathbb{E}\left[|\mathcal{C}|\right]=\sum_{t=3}^{\frac{1}{3}\log
n-1}\mathbb{E}\left[|C_{t}|\right]\leq\sum_{t=3}^{\frac{1}{3}\log
n-1}4^{t}<4^{\frac{1}{3}\log n}=n^{\frac{2}{3}}\leavevmode\nobreak\ .$

By Markov inequality, $\Pr\left[|\mathcal{C}|\geq
n\right]\leq\frac{\mathbb{E}\left[|\mathcal{C}|\right]}{n}<n^{-\frac{1}{3}}<\frac{1}{2}$.
By union bound, there exists a graph $G$ with at least $3n$ edges, and at most
$n$ cycles of length less than $\frac{1}{3}\log n$. Let $G^{\prime}$ be the
graph obtained by deleting an arbitrary single edge from each cycle. Continue
deleting edges until $G^{\prime}$ has exactly $2n$ edges. We conclude that
$G^{\prime}$ has $2n$ edges and girth at least $\frac{1}{3}\log n$ as
required. ∎

###### Proof of Lemma 13.

Fix $\delta=\frac{1-\epsilon}{2\epsilon}$. Set $n^{\prime}=\epsilon
n=\frac{n}{1+2\delta}$. We ignore issues of integrality during the proof. Such
issues could be easily fixed as we don’t state an explicit bound on the girth.
Using 2, construct a graph $G^{\prime}$ with $n^{\prime}$ vertices,
$2n^{\prime}$ edges, and girth $\Omega(\log n^{\prime})$.

Let $G$ be the graph obtained from $G^{\prime}$ by replacing each edge with a
path of length $\delta+1$. Then:

$\displaystyle|V(G)|$
$\displaystyle=|V(G^{\prime})|+\delta\cdot|E(G^{\prime})|=n^{\prime}+\delta\cdot
2n^{\prime}=n^{\prime}(1+2\delta)=n$ $\displaystyle|E(G)|$
$\displaystyle=(\delta+1)\cdot|E(G^{\prime})|=(\delta+1)\cdot
2n^{\prime}=n\cdot\frac{2(1+\delta)}{1+2\delta}=(1+\epsilon)n\leavevmode\nobreak\
,$

where the last equality follows by the definition of $\delta$. Note that the
girth of $G$ is at least $\Omega((1+\delta)\log
n^{\prime})=\Omega(\frac{\log\epsilon n}{\epsilon})=\Omega(\frac{\log
n}{\epsilon})$, for $n$ large enough. ∎

The _Euler characteristic_ of a graph $G$ is defined as
$\chi(G)\coloneqq|E(G)|-|V(G)|+1$. Our lower bound is based on the following
theorem by Rabinovich and Raz [RR98].

######  Theorem 11 ([RR98] ).

Consider an unweighted graph $G$ with girth $g$, and consider a (classic)
embedding $f:G\rightarrow H$ of $G$ into a weighted graph $H$, such that
$\chi(H)<\chi(G)$. Then $f$ has multiplicative distortion at least
$\frac{g}{4}-\frac{3}{2}$.

Next, we transfer the language of classic embeddings into graphs used in
Theorem 11 to that of clan embeddings into trees.

######  Lemma 14.

Consider an unweighted, $n$-vertex graph $G=(V,E)$ with girth $g$, and let
$(f,\chi)$ be a clan embedding of $G$ into a tree $T$ with multiplicative
distortion $t<\frac{g}{4}-\frac{3}{2}$. Then necessarily $\sum_{v\in
V}|f(v)|\geq n+\chi(G)$.

###### Proof.

Let $H$ be the graph obtained from $T$ by merging all the copies of each
vertex. Specifically, arbitrarily order the vertices in $V$:
$v_{1},v_{2},\dots,v_{n}$. Iteratively construct a series of graphs
$H_{0}=T,H_{1},H_{2},\dots,H_{n}$ with one-to-many embeddings
$f_{i}:G\rightarrow H_{i}$. In the $i$’th iteration, we create $H_{i},f_{i}$
out of $H_{i-1},f_{i-1}$ by replacing all the vertices in $f_{i-1}(v_{i})$ by
a single vertex $\tilde{v}_{i}$. For a vertex $u\in H_{i-1}$, we add an edge
from $u$ to $\tilde{v}_{i}$ if there was an edge from $u$ to some vertex in
$f_{i-1}(v)$. If an edge $\\{u,\tilde{v}_{i}\\}$ is added, its weight is
defined to be $\min_{v^{\prime}\in f_{i-1}(v)}w_{H_{i-1}}(v^{\prime},u)$. Set
$H=H_{n}$, and $\tilde{f}=f_{n}$. Clearly, distances in $H$ can only decrease
compared to $T$. This is because for every $u,v\in V$,
$d_{H}(\tilde{u},\tilde{v})\leq\min_{u^{\prime}\in f(u),\leavevmode\nobreak\
v^{\prime}\in f(v)}d_{T}(u^{\prime},v^{\prime})\leq\min_{u^{\prime}\in
f(u)}d_{T}(u^{\prime},\chi(v))\leq t\cdot d_{G}(u,v)$. On the other hand, by
induction (and the triangle inequality), since $f$ is a dominating embedding,
one can show that $\tilde{f}$ is also dominating. That is $\forall u,v\in V$,
$d_{H}(\tilde{u},\tilde{v})\geq d_{G}(u,v)$.

We conclude that $\tilde{f}$ is a classic embedding of $G$ with a
multiplicative distortion at most $t<\frac{g}{4}-\frac{3}{2}$. By Theorem 11,
it follows that $\chi(H)\geq\chi(G)$. For every $i$, it holds that

$\chi(H_{i})=|E(H_{i})|-|V(H_{i})|-1\leq|E(H_{i-1})|-\left(|V(H_{i-1})|-|f(v_{i})|+1\right)-1=\chi(H_{i-1})+|f(v_{i})|-1$

As the Euler characteristic of a tree equals $0$, we obtain

$\chi(G)\leq\chi(H)=\chi(H_{n})\leq\sum_{i}(|f(v_{i})|-1)+\chi(T)=\sum_{v\in
V}|f(v)|-n\leavevmode\nobreak\ ,$

as desired. ∎

We are now ready to prove Theorem 2.

###### Proof of Theorem 2.

For the first assertion, using Lemma 13, let $G$ be an unweighted graph with
girth $g=\Omega(\frac{\log n}{\epsilon})$ and $(1+\epsilon)n$ edges. Consider
a clan embedding of $G$ into a tree with distortion smaller than
$\frac{g}{4}-\frac{3}{2}=\Omega(\frac{\log n}{\epsilon})$. By Lemma 14, it
holds that

$\sum_{v\in V}|f(v)|\geq n+\chi(G)=|E(G)|+1>(1+\epsilon)n\leavevmode\nobreak\
.$

The second assertion follows similar lines. Set
$g=2\cdot\left\lfloor\frac{\frac{4}{3}k+2}{2}\right\rfloor$. Note that $g$ is
largest even number up to $\frac{4}{3}k+2$. Using Theorem 10, let $G$ be an
unweighted graph with girth $g$ and
$\Omega(n^{1+\frac{4}{3}\cdot\frac{1}{g-2}})\geq\Omega(n^{1+\frac{1}{k}})$
edges. Consider a clan embedding of $G$ into a tree with distortion smaller
than $\frac{g}{4}-\frac{3}{2}=\Omega(k)$. By Lemma 14, it holds that

$\sum_{v\in V}|f(v)|\geq
n+\chi(G)=|E(G)|+1=\Omega(n^{1+\frac{1}{k}})\leavevmode\nobreak\ .$

∎

##  6 Ramsey Type Embedding for Minor-Free Graphs

This section is devoted to proving the following theorem, See 4 We begin by
proving Theorem 4 for the special case of nearly-$h$-embeddable graphs.

######  Lemma 15.

Given a nearly $h$-embeddable $n$-vertex graph $G=(V,E,w)$ of diameter $D$,
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 treewidth $O_{h}(\frac{\log n}{\epsilon\delta})$ graphs, such that there
is a subset $M\subseteq V$ of vertices for which the following claims hold:

  1. 1.

For every clique $Q\subseteq V$, $\Pr[Q\subseteq M]\geq 1-\delta$.

  2. 2.

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

###### Proof.

Consider a nearly $h$-embedded graph $G=(V,E,w)$. Assume w.l.o.g. that $D=1$,
otherwise we will 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$. Let $\varPsi$ be the
set of apices. We will construct $q=\frac{5}{\delta}$ embeddings, all
satisfying property (2) of Lemma 15. The final embeddings will be obtained by
choosing one of these embeddings uniformly at random. We first create a new
graph $G^{\prime}=G[V\setminus\varPsi]$ by deleting all the apex vertices