Tree-Like Shortcuttings of Trees

Low-treewidth shortcutting was introduced in the context of low-treewidth embedding of planar metrics. Specifically, Filtser and Le [16] showed that if one can construct a tree shortcutting with hop-diameter $k$ and treewidth $t$, then one obtains an embedding of planar metrics into graphs of treewidth $O(kt/ϵ)$ and additive distortion $+ϵD$, where $D$ is the diameter of the input metric. They constructed a tree shortcutting with hop-diameter $k=O(\log \log n)$ and treewidth $t=O(\log \log n)$, and hence obtained an embedding with treewidth $O({(\log \log n)}^2/ϵ)$. This bound does not seem to be optimal – other works [17, 11] used different embedding techniques to remove the dependency on $n$ but at the cost of a (much) higher dependency on $1/ϵ$. If one can construct a shortcutting with hop-diameter $k=O(1)$ and treewidth $t=O({\alpha }_k(n))$ (which matches the sparsity bound), then one gets an embedding of planar metrics with treewidth $O({\alpha }_k(n)/ϵ)=O({\log }^{\ast }(n)/ϵ)$, which is almost as good as $O(1/ϵ)$. The linear dependency on $1/ϵ$ is optimal [16], whereas the other embedding techniques [17, 11] have an inherent $\mathrm{\Omega }(1/{ϵ}^2)$ barrier. Motivated by this observation, Filtser and Le [16] asked:

In this work, we seek to answer a broader question: What is the exact tradeoff between the hop-diameter $k$ and the treewidth $t$ of tree shortcuttings? Understanding the full tradeoff would not only answer Question 1 but could also be useful for other applications that require a different hop-diameter. Specifically, in this paper, we use our construction for $k=3$ to resolve an open problem posed by Kahalon et al. [18] regarding compact routing schemes.

Given a set of points $P$ in an Euclidean (or doubling) space of dimension $d$, one can construct a sparse $(1+ϵ)$-spanner with a small hop-diameter. This is achieved via tree covers. (See Section 2 for a definition.) Known tree cover constructions for Euclidean and doubling metrics achieve stretch $1+ϵ$ using ${ϵ}^{-O(d)}$ trees [4, 5, 12]. By constructing a $k$-hop shortcutting $G_T$ for each tree $T$ in the cover $𝒯$, the union ${\cup }_{T\in 𝒯}{G}_T$ is a $k$-hop $(1+ϵ)$-spanner. For a constant $ϵ$ and $d$, the sparsity is only $O(1)$ times worse than the sparsity of the shortcuttings, which is $O({\alpha }_k(n))$. However, if $G_T$ has low treewidth for every tree $T$, the union ${\cup }_{T\in 𝒯}{G}_T$ might have a very large treewidth. A recent work on low-treewidth Euclidean spanners by Buchin, Rehs, and Scheele [8] showed that treewidth-$t$ spanners must have stretch $\mathrm{\Omega }(n/t^{d/(d-1)})$. That is, if the stretch is $O(1)$, the treewidth has to be very large: $\mathrm{\Omega }(n^{1-1/d})$.

While the treewidth grows substantially under taking union, the arboricity does not: if $G_T$ has arboricity at most $\beta$ for every $T\in 𝒯$, then ${\cup }_{T\in 𝒯}{G}_T$ has arboricity $|𝒯|\beta$, which is $O(\beta )$ for constant $ϵ$ and $d$. This makes arboricity an appealing tree-like measure. Specifically, one could hope to construct a low-arboricity Euclidean (or doubling) $(1+ϵ)$-spanner with small hop-diameter using low-arboricity tree shortcuttings.

A tree decomposition of $G=(V,E)$ is a tree $T$ where each node is associated with a subset of $V$ called a bag. The bags $X_1,\mathrm{\dots },X_{\mathrm{\ell }}$ satisfy: (i) ${\cup }_{i=1}^{\mathrm{\ell }}{X}_i=V$, (ii) for every vertex $v\in V$, the collection of bags containing it forms a connected subtree of $T$, and (iii) for every edge $(u,v)\in E$, there is a bag containing $u$ and $v$. The width of $T$ is ${\max }_{i=1}^{\mathrm{\ell }}|X_i|-1$; the treewidth of $G$ is the minimum width among all possible tree decompositions of $G$. If a graph $G$ contains $K_h$ as a minor, then the treewidth of $G$ is at least $h-1$.

The arboricity of $G=(V,E)$ is defined as $\max \lceil \frac{|E(H)|}{|V(H)|-1}\rceil$, where the maximum is taken over all subgraphs $H$ of $G$ with at least two vertices.

Given a metric space $M_X=(X,\delta )$, which we view as a complete graph $(X,\left(\genfrac{}{}{0pt}{}{X}{2}\right))$, a $t$-spanner of $M_X$ is a subgraph $H=(X,E)$ with $E\subseteq \left(\genfrac{}{}{0pt}{}{X}{2}\right)$, such that for every two vertices $x,y\in X$, their distance in $H$ is at most $t\cdot \delta (x,y)$. The path $P_{x,y}$ realizing this distance is called a $t$-spanner path. The hop-diameter of a spanner is the minimum $k$ such that between every two vertices $x,y\in X$ there is a $t$-spanner path with at most $k$ edges.

Given a metric space $M_X=(X,\delta )$, a tree cover of $M_X$ with stretch $t$ is a collection of trees such that for every two vertices $x,y\in X$ we have $\delta (x,y)\le {\min }_{T\in 𝒯}{\delta }_T(x,y)\le t\cdot \delta (x,y)$, where ${\delta }_T(x,y)$ is the distance between $x$ and $y$ in $T$.

We prove the claim by complete induction over $n$. For the base case, we use $n=1$, where the claim holds vacuously. Let $H$ be a shortcutting for $L$ with hop-diameter 2. Split $L$ into two consecutive parts, $L_1$ and $L_2$, of sizes $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, respectively. Let $H_1$ and $H_2$ be subgraphs of $H$ induced on $L_1$ and $L_2$, respectively. From the induction hypothesis, $H_1$ and $H_2$ have $K_{\log \lfloor n/2\rfloor +1}$ and $K_{\log \lceil n/2\rceil +1}$ as minors, respectively. Consider the case where every point of $L_1$ has an edge in $H$ to some point in $L_2$. Then $K_{\log \lfloor n/2\rfloor }\cup \{H_2\}$ induces a clique minor of size $\log \lfloor n/2\rfloor +1$. Consider the complementary case where $L_1$ has a point $p$ that does not have an edge in $H$ to any point in $L_2$. Then, every point in $L_2$ has a neighbor in $L_1$ because $H$ has hop-diameter $2$. Thus, $K_{\log \lceil n/2\rceil }\cup \{H_1\}$ induces a clique minor of size $\log \lceil n/2\rceil +1$. Hence, the minor size satisfies recurrence $W_2(n)\ge W_2(\lfloor n/2\rfloor )+1$, with a base case $W_2(1)=1$. The solution is given by $W_2(n)=\lfloor \log n\rfloor +1$. $◀$

We next give a proof for even values of $k$ such that $4\le k\le \frac{2}{\ln (2e)}\ln \log n$ in Lemma 7. The proof for odd values is analogous. The proof for $k>\frac{2}{\ln (2e)}\ln \log n$ is given in Lemma 8. We will need some auxiliary claims (Claims 9, 11, and 10) in the proofs of Lemmas 7 and 8, as well as in the upper bound proof of Theorem 3. These claims are deferred to the end of this section.

We prove the statement by complete induction over $n$ and $k$. For the base case, we take $n=1$, and $W_k(1)=1>c_{1}k{\log }^{2/k}n-1$. Otherwise, let ${\mathrm{\ell }}_k$ be such that $\log {\mathrm{\ell }}_k={(\frac{k}{k-2})}^{(k-2)/2}{(\log n)}^{(k-2)/k}$ for even values of $k$. (The proof for odd values is similar. There, we choose ${\mathrm{\ell }}_k$ so that $\log {\mathrm{\ell }}_k={(\frac{k}{k-2})}^{(k-2)/2}{(\log n/\log \log n)}^{(k-2)/k}$.) By Claim 10, we have that ${\mathrm{\ell }}_k\le \sqrt{n}$, whenever $k\le \frac{2}{\ln (2e)}\ln \log n$.

Split $L$ into consecutive sets of points $L_1,L_2,\mathrm{\dots },L_{{\mathrm{\ell }}_k}$ of size $\lfloor n/{\mathrm{\ell }}_k\rfloor$ each and ignore the remaining points. Let $H$ be a shortcutting with hop-diameter $k$ for $L$. Our goal is to show that the size of a clique minor of $H$ can be lower bounded by the following recurrence.

We say that a point in $L_i$ is global if it has an edge to a point outside $L_i$ and non-global otherwise. We say that $L_i$ is global if all of its points are global and non-global otherwise.

See Figure 1 for an illustration. For every $L_i$ and $L_j$ the path between a non-global point in $L_i$ and a non-global point in $L_j$ must have the first (resp., last) edge inside $L_i$ (resp., $L_j$). Let $H^{\prime }$ be obtained from $H$ by contracting each $L_i$ into a single vertex. (Clearly, $H[L_i]$ is connected.) Let $L^{\prime }$ be the path obtained from $L$ by contracting every $L_i$ into a single point. Then $H^{\prime }$ is a $(k-2)$-hop spanner of $L^{\prime }$ with stretch 1. Thus, $H^{\prime }$ has a minor of size $W_{k-2}({\mathrm{\ell }}_k)\ge c_1(k-2){\log }^{2/(k-2)}{\mathrm{\ell }}_k-1=c_{1}k{\log }^{2/k}n-1$.

See Figure 2 for an illustration. Let $\{L_l,L_r\}=L\setminus L_i$, so that $L_l$ (resp., $L_r$) is on the left (resp., right) of $L_i$. (Possibly $L_l=\mathrm{\varnothing }$ or $L_r=\mathrm{\varnothing }$.) At least $|L_i|/2$ points in $L_i$ have edges to either $L_l$ or $L_r$. Without loss of generality, we assume the latter. Let $L_i^{\prime }\subseteq L_i$ be the subset of points that have edges to $L_r$ and let $H_i$ be a subgraph of $H$ which is a shortcutting of $L_i$ with hop-diameter $k$. Inductively, $H_i$ has a clique minor of size at least $W_k(n/(2{\mathrm{\ell }}_k))$. (Since $H_i$ is a $1$-spanner, it does not include any point outside of $L_i$.) Then $H_i$ and $L_r$ are vertex-disjoint (because we are considering $1$-spanners) and hence their union has a clique minor of size $W_k(n/(2{\mathrm{\ell }}_k))+1$. Thus, $W_k(n)$ satisfies Equation 1, which we lower bound next.

The last inequality follows from Claim 9 by replacing $c_1=1/\gamma$, $x=\log n$ and $\alpha =1$. $◀$

We set ${\mathrm{\ell }}_k$ so that $\log \log {\mathrm{\ell }}_k=\sqrt{\frac{k-2}{k}}\log \log n$. (We use $\log (\cdot )≔{\log }_2(\cdot )$.) For the clarity of exposition, we ignore the rounding issues. We note that $1\le {\mathrm{\ell }}_k\le n$. Using the same argument as in Lemma 7, we have $W_k(n)\ge \min (W_{k-2}({\mathrm{\ell }}_k),W_k(n/(2{\mathrm{\ell }}_k))+1)$. We prove the lemma by induction, where the base case is Lemma 7 whenever . Our goal is to prove that $W_{k-2}({\mathrm{\ell }}_k)\ge c_2{(\log \log n)}^2/k$ and $W_k(n/(2{\mathrm{\ell }}_k))+1\ge c_2{(\log \log n)}^2/k$. For the first inequality we distinguish two cases. If $k-2\le \frac{2}{\ln (2e)}\ln \log ({\mathrm{\ell }}_k)$, then by Lemma 7 we have

The penultimate inequality holds because $k\ge \frac{2}{\ln (2e)}\ln \log (n)\ge \frac{2}{\ln (2e)}\ln \log ({\mathrm{\ell }}_k)$. The last inequality holds for a proper choice of constant $c_2$. If $k-2>\frac{2}{\ln (2e)}\ln \log ({\mathrm{\ell }}_k)$, we have $W_{k-2}({\mathrm{\ell }}_k)\ge c_2\frac{{(\log \log {\mathrm{\ell }}_k)}^2}{k-2}$ by the induction hypothesis. Hence, in both cases, we have:

For the second inequality, let $x=\log n$. We have $\log {\mathrm{\ell }}_k=x^{\sqrt{(k-2)/k}}$. Since , we have that $k>\frac{2}{\ln (2e)}\ln \log \frac{n}{2{\mathrm{\ell }}_k}$ and the induction hypothesis gives the following.

To show that the right-hand side is at least $c_2{\log }^2(x)/k$, it suffices to show the following:

From Claim 11 we have $x^{\sqrt{(k-2)/k}}\le x-\frac{x\ln x}{k}+\frac{x{\ln }^{2}x}{k^2}$.

The last inequality holds because $k>\frac{2}{\ln (2e)}\ln (x)$. We next consider two cases. If , then $\frac{k}{c_2}>\frac{x\ln x}{20c_2}\ge {\log }^{2}x$ and Equation 2 is proved. Otherwise, we proceed as follows.

The last inequality holds for any $c_2\le 1/10$. $◀$

We conclude the section by proving the auxiliary claims used in the lemmas above.

We rewrite the expression as follows.

Using Maclaurin expansion, we have that ${(1+y)}^{2/k}=1+\frac{2}{k}y+\frac{2-k}{k^2}\cdot {(1+\zeta )}^{\frac{2}{k}-2}\cdot y^2$, where $\zeta$ is a number between $0$ and $y$. We set $y=-{\left(\frac{k}{k-2}\right)}^{(k-2)/2}\cdot x^{-2/k}-\alpha x^{-1}$.

Plugging Equation 4 into Equation 3, we obtain the following.

The lower bound in Claim 9 holds because and $x>1$. Next we prove the upper bound.

The right-hand side is decreasing with $x$ in the whole domain and we can upper bound it by taking $x=1$.

Letting $\gamma =(e+1)(e+3)$, the upper bound from Claim 9 follows. $\mathrm{⊲}$

We have that $k\le \frac{2}{\ln (2e)}\ln \log n$. Rearranging the last inequality, we have that $e{(\log n)}^{(k-2)/k}\le (\log n)/2$. The proof is completed by observing that ${(\frac{k}{k-2})}^{(k-2)/2}$ is monotonically increasing for $k\ge 3$ and ${lim}_{k\to \mathrm{\infty }}{(\frac{k}{k-2})}^{(k-2)/2}=e$. $\mathrm{⊲}$

Let $p≔1/k$. Then, $x^{\sqrt{(k-2)/k}}=x^{\sqrt{1-2p}}$. Using Taylor series around $p=0$, we have that $x^{\sqrt{1-2p}}=x-px\ln x+R(p)$. The term $R(p)$ has the following form for .

To complete the proof, we replace $p$ by $1/k$. $\mathrm{⊲}$