Optimal Bounds for Spanners and Tree Covers in Doubling Metrics

We give a negative answer to Question 1 by a surprisingly simple and tight lower bound.

Since the net-tree spanner has sparsity ³³3The sparsity of a spanner $H$ is the ratio between number of edges in $H$ over $n-1$, for $n>1$. $O({\epsilon }^{-d})$ [22], our lower bound shows, in particular, that the net-tree spanner is optimal; this is our key conceptual contribution.

Second, as our main technical contribution, we show that a tree cover with constant degree and nearly optimal size is achievable, resolving Question 2 affirmatively.

To complement our result, Theorem 3 shows that it is impossible to eliminate the $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(1/\epsilon )$ factor from the size of any constant-degree tree cover (the detailed proof is provided in Appendix A of the full version of this paper).

Theorem 3 demonstrates an inherent multiplicative gap of $\log (1/\epsilon )$ between the maximum degree and the optimal sparsity of $(1+\epsilon )$-spanners in doubling metrics, a gap that does not appear in Euclidean spaces. Although Theorem 3 is not the main focus of our work, it provides an interesting separation between Euclidean and doubling metrics. Moreover, it shows that the $\mathrm{𝗉𝗈𝗅𝗒𝗅𝗈𝗀}(1/\epsilon )$ term in Theorem 2 (hidden via the $\tilde{O}$-notation) is unavoidable in doubling metrics, whereas its necessity in Euclidean spaces remains an open question.

Our tree cover construction provides the key technical contribution of this work. In what follows, we provide a technical overview of this construction.

Our tree cover construction relies on a hierarchical structure – specifically, the standard net-tree – and builds a tree cover so that every cross edge $e$ (i.e., every edge in $E_i$) is contained in some tree. For every pair of points $(u,v)$, there exists a cross edge $(u^{\prime },v^{\prime })$ such that the path from $u$ to $v$ that goes through $(u^{\prime },v^{\prime })$ provides a good approximation of $d_X(u,v)$. The distance between $u$ and $v$ is then preserved by the tree $T$ that contains $(u^{\prime },v^{\prime })$; in this case, we say that $(u,v)$ is covered by $T$.

The construction proceeds in two phases. In Phase 1, we partition the cross edges into congruent classes according to their levels modulo $\log (1/\epsilon )$, and handle each class independently. For each class, we distribute the cross edges into each tree in our tree cover. Note that after Phase 1, we already obtain a tree cover of stretch $(1+\epsilon )$ and size $\tilde{O}({\epsilon }^{-d})$. In Phase 2, for a fixed level, we replace edges in a controlled manner to obtain the required bounded degree property, without significantly increasing the stretch. The desired $(1+\epsilon )$ stretch bound can then be recovered by a simple scaling argument.

Our Phase 2 is inspired by the degree-reduction procedure of [13]. To achieve constant degree, we proceed in two steps. First, using the technique in [8], we reroute the edges in each tree $T$ in the cover produced by Phase 1, obtaining trees of maximum degree ${\epsilon }^{-O(d)}$, while the stretch increases only to $1+O(\epsilon )$. Second, we use the rerouting technique in [13] to obtain absolute constant maximum degree. For each vertex $u$ in each such tree $T$, we replace the edges connecting $u$ to its children by a binary tree. Suppose that $l$ is the maximum distance from (the representative of) $u$ to its children, this step incurs an additive distortion of $\mathrm{\Theta }(\log ({\epsilon }^{-d})\cdot l)$ for every pair of points covered by $T$.

A key technical challenge in integrating Phase 2 into Phase 1 is that the edges replaced by binary trees must be sufficiently short relative to the cross edges at the same level. Otherwise, the additive distortion for a pair $(u,v)$ might become comparable to $d(u,v)$ itself, producing a stretch larger than 2. In the construction of [5], a point $u$ in a tree $T$ may be incident to ${\epsilon }^{-d}$ cross edges of nearly equal length; applying Phase 2 on top of [5] would therefore not yield a tree cover with good stretch.

Our first idea is to ensure that, in Phase 1, for every level we partition the cross edges into $O({\epsilon }^{-d})$ sets such that in each tree of the resulting cover, every point $u$ is incident to at most one edge from each set. This motivates partitioning $E_i$ into sets of matchings.

We implement Phase 1 as follows. We initialize tree cover $𝒯$ with $\tilde{O}({\epsilon }^{-d})$ empty forests. For each congruent class modulo $\log (1/\epsilon )$, we process the levels in increasing order. For each level $i$, we partition $E_i$ into sets of matchings ${ℳ}_i$. For each matching $M\in {ℳ}_i$, we assign $M$ to forest $F\in 𝒯$, and add all edges in $M$ to $F$. We continue this process until the top level.

A second challenge is ensuring that the graph $F$ remains a forest after inserting the edges of $M$. Specifically, we guarantee that for any two edges $(u,v)$ and $(u^{\prime },v^{\prime })$ in $M$, there is no tree in the forest $F$ containing both $u$ and $u^{\prime }$. This leads to our second idea: each matching $M$ must be pairwise far. That is, for every $M\in {ℳ}_i$ and every two distinct edges $e,e^{\prime }\in M$, the distance between (any two endpoints of) $e$ and $e^{\prime }$ must be at least $\mathrm{\Theta }(2^i)$. Under this condition, an inductive argument shows that every tree in each forest $F$ has small diameter (); thus, after connecting each tree to an edge in $M$, a sufficient separation still remains, ensuring that the resulting graph is indeed a forest. Such matchings, also known as red–blue matchings, were also used by [21, 36] in different contexts.

We first give a construction of a tree cover with maximum degree $O({\epsilon }^{-d}{\log }_{1/\epsilon }\mathrm{\Delta })$. Later, in Section 4.2, we modify this tree cover to get constant degree bound.

1. 1.

   Creating intra-level edge matchings. Let ${\delta }_p=2^p$ for $p\in \{0,\mathrm{\dots },\lfloor \log (1/\epsilon )\}\rfloor$, and let ${\tau }_{{\delta }_p}$ be a $({\delta }_p,{\epsilon }^{-1})$-net tree (see Definition 5) of $X$ and $N_i$ be the ${\delta }_p{\epsilon }^{-i}$-net in ${\tau }_{{\delta }_p}$. For each $p$, construct graph $G_p$, where $V(G_p)={\{u_i\mid u\in N_i\}}_{\forall i\in \mathbb{N}}$ and $E(G_p)=\mathrm{\varnothing }$. Define a set of cross edges $E_c={\{(u_i,v_i)\mid d_X(u,v)\in (\frac{{\delta }_p}{3{\epsilon }^{i+1}},\frac{4\cdot {\delta }_p}{3{\epsilon }^{i+1}})\}}_{\forall i}$. Partition $E_c$ into $\gamma =O({\epsilon }^{-d})$ matchings $ℳ=\{M_1,\mathrm{\dots },M_{\gamma }\}$, with the property that in each $M\in ℳ$, $d_X(u_i,v_i)>\frac{14{\delta }_p}{{\epsilon }^i}$, for all matched $u_i$, $v_i$. Initialize $T_k^p=(V(G_p),M_k)$ for $k\in \{1,\mathrm{\dots },\gamma \}$.

2. 2.

   Creating inter-level edges. For each $T=T_k^p$, construct edges between levels $i$ and $(i-1)$ in the order $i=0,1,\mathrm{\dots }$. Create a relabel function ${\mathrm{\Phi }}_i^T:N_i\stackrel{}{\to }{N}_i$, initialized as ${\mathrm{\Phi }}_i^T(u_i)=u_i$ for all $u_i\in N_i$. At each level $i$, process vertices in the order specified below:

   1. (a)

      Matched vertices. For each matched $u_i$ in $M_k$, add $(u_i,u_{i-1})$. For $v\in B_X(u,\frac{4{\delta }_p}{{\epsilon }^i})$ such that $v_{i-1}$ exists, add $(u_i,v_{i-1})$ if either $v_{i-1}$ is unmatched, or $(v_{i-1},x_{i-1})\in M_k$ and $x_{i-1}$ does not have a parent at level $i$.

   2. (b)

      Unmatched vertices. For each unmatched $u_i$: enumerate its child nodes in net-tree ${\tau }_{{\delta }_p}$, denoted by $C_{u_i}=\{a_{i-1}^0,a_{i-1}^1,\mathrm{\dots },a_{i-1}^{\eta }\}$. For every $a_{i-1}\in C_{u_i}$:

      • $\mathrm{■}$

        Add $({\mathrm{\Phi }}_i^T(u_i),a_{i-1})$ in the following cases: 1) $a_{i-1}$ is unmatched and does not have a parent, and 2) $(a_{i-1},b_{i-1})\in M_k$ and both $a_{i-1}$, $b_{i-1}$ do not have parents at level $i$.

      • $\mathrm{■}$

        Otherwise, if $a_{i-1}$ has a parent $x_i$, or $(a_{i-1},b_{i-1})\in M_k$ and $b_{i-1}$ has a parent $x_i$, merge $x_i$ with ${\mathrm{\Phi }}_i^T(u_i)$. Set ${\mathrm{\Phi }}_i^T(x_i)={\mathrm{\Phi }}_i^T(u_i)$ if $u_{i+1}$ exists, otherwise set ${\mathrm{\Phi }}_i^T(u_i)=x_i$. (Note that $a_{i-1}$ and $b_{i-1}$ will not have parents at the same time.)

3. 3.

   Contraction. Contract all vertices sharing label $u$. $𝒯={\{T_k^p\}}_{p,k}$ forms a tree cover.

Throughout the construction (even after relabeling), the weight of any edge, $w_T(u_i,v_j)=d_X(u,v)$. In Step 2, we slightly abuse the notation, setting ${\mathrm{\Phi }}_i^T(u_i)=x_i$, instead of ${\mathrm{\Phi }}_i^T({\mathrm{\Phi }}_i^T(u_i))=x_i$. This is fine, since a node undergoes relabeling at most once. This finishes the construction of the tree cover.

Unless stated otherwise, we refer to the intermediate trees just prior to Step 3 as the tree cover $𝒯$ and prove our bounds on them. This works since the contraction of only 0-weight edges in Step 3 does not affect the stretch.

We first prove that each $T$ in $𝒯$, after contraction, is a tree (see Corollary 16). Then, we bound the number of trees in $𝒯$ (see Lemma 17). Finally, we use Claim 18 and Claim 19 to bound the final stretch in Lemma 20 (proof deferred to the Appendix B of the full version).

We first require the following combinatorial lemma of [21], used in Step 1 of our construction.

We begin by proving that each $T_k^p\in 𝒯$ is a tree. We rely on the following inductive invariant: after processing the $i^{th}$ level, every level-$i$ subtree has a diameter at most $O(\epsilon )$ factor of the newly added level-$i$ cross edge. This large separation ensures that the forest remains a forest.