Light Spanners with Small Hop-Diameter

When $n\le k$, the tree $T$ already has hop-diameter $k$. If $k=1$, the procedure construct a clique on $T$ and the lemma holds immediately. (Recall that every edge in $F$ has weight equal to the distance of its endpoints in $T$.)

Next we analyze the case $k=2$. Consider two vertices $u$ and $v$ in $T$ and consider the last recursion level where both $u$ and $v$ were in the same tree, $T^{\prime }$. The centroid vertex $c^{\prime }$ of $T^{\prime }$ is connected via an edge to both $u$ and $v$. Vertex $c^{\prime }$ is on the shortest path in $T^{\prime }$ between $u$ and $v$, because after the removal of $c^{\prime }$, vertices $u$ and $v$ are not in the same subtree anymore by the choice of $T^{\prime }$. Hence, there is a 2-hop path between $u$ and $v$, consisting of edges $(u,c^{\prime })$ and $(c^{\prime },v)$. By construction, the weight of this path is ${\delta }_T(u,c^{\prime })+{\delta }_T(c^{\prime },v)={\delta }_T(u,v)$, where the equality holds because $c^{\prime }$ is on the shortest path between $u$ and $v$.

It remains to analyze the case $k\ge 3$. Consider two vertices $u$ and $v$ in $T$ and consider the last recursion level where both $u$ and $v$ were in the same tree, $T^{\prime }$. Let $X^{\prime }$ be the subset of $V(T^{\prime })$ that is used in the construction to split $T$ into connected components. Let $T_u$ and $T_v$ be the connected components containing $u$ and $v$, respectively. By the choice of $T^{\prime }$, the components $T_u$ and $T_v$ are different. Let $u^{\prime }$ and $v^{\prime }$ be the vertices in $X^{\prime }$ such that $u^{\prime }$ is neighboring $T_u$, $v^{\prime }$ is neighboring $T_v$ and $u^{\prime }$ and $v^{\prime }$ lie on the shortest path between $u$ and $v$. Such a vertex $u^{\prime }$ exists because all the shortest paths stemming from $T_u$ and going outside of $T_u$ contain one of the at most two vertices in $X$ that neighbors $T_u$. The argument is analogous for $v^{\prime }$. From the construction, we know that the constructed spanner contains edges $(u,u^{\prime })$ and $(v^{\prime },v)$. Recall that the vertices in $X$ are connected recursively using a construction for hop-diameter $k-2$. This means that there is a path between $u$ and $v$ with at most $k-2+2=k$ hops. (It is possible that $u^{\prime }=v^{\prime }$, but this case is handled similarly.) The stretch of the path between $u^{\prime }$ and $v^{\prime }$ is 1 by the induction hypothesis. The weights of edges $(u,u^{\prime })$ and $(v,v^{\prime })$ correspond to the underlying distances of their endpoints in $T$. Since $u^{\prime }$ and $v^{\prime }$ lie on the shortest path between $u$ and $v$ in $T$, the weight of the spanner path between $u$ and $v$ is equal to their distance in $T$. $◀$

The lemma is implied by the following claims.

The claim is true because the algorithm returns the edge set of $T$ in this case. $\mathrm{⊲}$

The claim is true because the algorithm returns the clique on the $n$ vertices of $V$. Each edge in the clique has weight at most $L$. The total weight is thus at most $\left(\genfrac{}{}{0pt}{}{n}{2}\right)L\le \frac{n^{2}L}{2}$. $\mathrm{⊲}$

We use $L_i$ to denote the weight of $T_i$ plus the weight of the edge connecting $T_i$ to $c$. Clearly, $L={\sum }_{i=1}^g{L}_i$. From the construction we have that $c$ is connected by an edge to each of the vertices of $T\setminus \{c\}$. The weight of these edges can be upper bounded by ${\sum }_{i=1}^g{n}_i{L}_i$, since for each $i\in [g]$, the edge between $c$ and a vertex in $T_i$ has weight of at most $L_i$. The construction proceeds recursively on each $T_i$, and the total weight incurred by recursion is at most ${\sum }_{i=1}^g{W}_2(n_i,L_i)$. We proceed to upper bound $W_2(n,L)$ inductively.

$\mathrm{⊲}$

Clearly, $L={\sum }_{i=1}^g{L}_i$. Recall that from Lemma 6, we have . For each $T_i$, $1\le i\le g$, the spanner construction adds an edge between each $v\in T_i$ and (at most two) vertices from $X$ which neighbor $T_i$. The total weight of these edges is at most $2{\sum }_{i=1}^g{n}_i{L}_i\le 2\mathrm{\ell }{\sum }_{i=1}^g{L}_i=2\mathrm{\ell }L$. The first inequality holds because each subtree has at most $n_i\le \mathrm{\ell }$ vertices. In addition, the vertices in $X$ are connected using a construction with hop-diameter $k-2$. The total weight of the edges used is at most $W_{k-2}(|X|,L)\le W_{k-2}(\frac{2n}{\mathrm{\ell }+1},L)$. Finally, each of the components $T_i$ is handled inductively and this contributes at most ${\sum }_{i=1}^g{W}_k(n_i,L_i)\le {\sum }_{i=1}^g{W}_k(\mathrm{\ell },L_i)$ to the weight. $\mathrm{⊲}$

When $k=3$, parameter $\mathrm{\ell }$ is set to $\lfloor n^{2/3}\rfloor$.

The last inequality holds for every $n\ge 4$. $\mathrm{⊲}$

When $k=1$, we have $W_1(n,L)\le \frac{n^2}{2}\cdot L\le 8nL$. When $k=2$, we have $W_2(n,L)\le nL$. For $k=3$ and $1\le n\le 3$, by Claim 9 we have $W_3(n,L)\le L$. It is straightforward to verify the bound for $k=3$ and $n\in \{4,5\}$. For $k=3$ and $n\ge 6$, the bound is implied by Claim 13 because $16n^{2/3}\le 9n$. Finally, when $k\ge 4$, parameter $\mathrm{\ell }$ is set to $k$ and the upper bound on $W_k(n,L)$ is obtained as follows.

$\mathrm{⊲}$

When $k=1$, we have $W_1(n,L)\le \frac{n^2}{2}\cdot L\le \frac{{(8k)}^2}{2}\cdot L\le 32kL$. When $k=2$, we have $W_2(n,L)\le nL\le 8kL$. When $k=3$, we have $W_3(n,L)\le 16n^{2/3}L\le 16\cdot {(8k)}^{2/3}L\le 64kL$. When $k\ge 4$, we have that $8k\le 2k^2$ and so $\mathrm{\ell }=k$.

$\mathrm{⊲}$

When $k=1$, we have $W_1(n,L)=\frac{n^2}{2}\cdot L\le \frac{{(2k^2)}^2}{2}\cdot L\le 2kL$. When $k=2$, we have $W_2(n,L)\le nL\le 2k^{2}L\le 4kL$. When $k=3$, we have $W_3(n,L)\le 16n^{2/3}L\le 16\cdot {(2k^2)}^{2/3}L\le 38kL$. When $k\ge 4$, we have $\mathrm{\ell }=k$.

$\mathrm{⊲}$

We have $\mathrm{\ell }=\lfloor 2n^{2/k}\rfloor$.

Rearranging, we have that . This means that $W_k(2n^{2/k},L_i)\le L_i$.

The last inequality holds for any $c\ge 5/2$.

Rearranging, we have that .

The last inequality is true for any $c\ge 23$.

The penultimate inequality holds because $k\cdot 2^{2/k}\cdot n^{\frac{4-2k}{k^2}}\le \sqrt{2}$ for $k\ge 4$ and $n\ge k^k$. The last inequality holds for any $c\ge 7$. $\mathrm{⊲}$

Partition $M$ into four consecutive parts, $M_1$, $M_2$, $M_3$, and $M_4$, each consisting of $p/4$ points. The distance between a point in $M_1$ and a point in $M_4$ is at least $\frac{p}{4}\cdot \frac{1}{n}$ and there is at least ${(p/4)}^2$ such pairs. Since every pair requires a direct edge, the total weight these edges incur is at least $\frac{p}{4n}\cdot \frac{p^2}{16}\ge \frac{1}{64}{\left(\frac{p^2}{n}\right)}^2$. $◀$

Partition $M$ into four consecutive parts, $M_1$, $M_2$, $M_3$, and $M_4$, each consisting of $p/4$ points. Consider two complementary cases. First, if every point in $M_1$ is incident on an edge that goes to either $M_3$ or $M_4$, the total weight of these edges is at least $\frac{p}{4}\cdot \frac{p}{4n}$. In the complementary case, there is a point $a$ in $M_1$ that is not incident on any edge that goes to $M_3$ or $M_4$. Consider an arbitrary point $b$ in $M_4$. A 2-hop path between $a$ and $b$ has to have the first edge between $a$ and a point in $M_1\cup M_2$ and the second edge between $M_1\cup M_2$ and $b$. The weight of the second edge is at least $p/(4n)$. Since every point in $M_4$ induces a different edge, the total weight is at least $\frac{p}{4}\cdot \frac{p}{4n}$. (See Figure 1 for an illustration.) In conclusion, both of the cases require total weight of $\frac{p}{n}\cdot \frac{p}{16}$ and the lower bound follows. $◀$

Let $H_k$ be an arbitrary spanner with hop-diameter $k$ of $M$. Partition $M$ into consecutive intervals, each containing $\mathrm{\ell }$ points where the value of $\mathrm{\ell }$ will be set later. We call an edge global if it has endpoints in two different intervals. We call a point global if it is incident on a global edge and non-global otherwise.

Consider an arbitrary interval and recall that it has length $\mathrm{\ell }/n$ and consists of $\mathrm{\ell }$ points. The interval contains at most $\frac{\gamma }{4}\cdot \mathrm{\ell }$ points that are at distance at most $\frac{\gamma }{4}\cdot \frac{\mathrm{\ell }}{n}$ from the left border of the interval. Hence, there are at most $2\cdot \frac{\gamma }{4}\cdot \mathrm{\ell }$ points that are at distance at most $\frac{\gamma }{4}\cdot \frac{\mathrm{\ell }}{n}$ from either of the interval borders. Summing over all the $n/\mathrm{\ell }$ intervals, we conclude that there is at most $2\cdot \frac{\gamma }{4}\cdot \mathrm{\ell }\cdot \frac{n}{\mathrm{\ell }}=\frac{\gamma n}{2}$ points that are at distance at most $\frac{\gamma \mathrm{\ell }}{4n}$ from the adjacent interval. The other $\frac{\gamma n}{2}$ points are at distance at least $\frac{\gamma \mathrm{\ell }}{4n}$. These points induce edges of total weight of at least $\frac{1}{2}\cdot \frac{\gamma n}{2}\cdot \frac{\gamma \mathrm{\ell }}{4n}$, where the factor $1/2$ comes from the fact that each edge might be counted twice. $\mathrm{⊲}$ Let ${\alpha }_0=\frac{1}{4e}$ and let ${\mathrm{\ell }}_0={\alpha }_0{n}^{2/k}$. We distinguish between two cases. Let ${\gamma }_0$ be the fraction of global points.

Proceed with case analysis below for $i=1$.

In this case, the fraction of the non-global points is $1-{\gamma }_0\ge 1/2$. We construct a new line metric, $M^{\prime }$ by taking a non-global point from every interval containing a non-global point. There are at $n^{\prime }=\frac{n}{{\mathrm{\ell }}_0}$ intervals and at least $p^{\prime }=(1-{\gamma }_0)\frac{n}{{\mathrm{\ell }}_0}$ of them contain a non-global point. (We ignore the rounding issues for simplicity of exposition.) Consider an interval $A$ containing a non-global point $a$ and an interval $B$ containing a non-global point $b$. Any $k$-hop path between $a$ and $b$ has to have the first edge inside of the interval $A$, towards some point $a^{\prime }$ and the last edge inside of interval $B$ towards some point $b^{\prime }$. Hence, $a^{\prime }$ and $b^{\prime }$ have to be connected via a $(k-2)$-hop path. This is true for any pair of non-global points in $M^{\prime }$. We use the induction hypothesis for $k-2$ to lower bound the total weight of $H_k$.

The following case analysis consists of cases $i$.1 and $i$.2 for $1\le i\le \lfloor {\log }_{32}(ek)\rfloor =i^{\prime }$. We let ${\alpha }_i=\frac{{32}^i}{4e}$ and ${\mathrm{\ell }}_i={\alpha }_i\cdot n^{2/k}$. We use ${\gamma }_i$ to denote the number of global points with respect to ${\mathrm{\ell }}_i$. (See Figure 2 for an illustration of the monotonicity of the number of global points.)

Proceed with $i+1$.

We have that ${\gamma }_{i-1}-{\gamma }_i\ge \frac{1}{4^i}$. This means that $\gamma ={\gamma }_{i-1}-{\gamma }_i$ fraction of the points are global with respect to ${\mathrm{\ell }}_{i-1}$ and are not global with respect to ${\mathrm{\ell }}_i$. Their total contribution, by Claim 22, is at least ${\gamma }^2{\mathrm{\ell }}_{i-1}/16$. Similarly to Case $0$.2 above, we employ the induction hypothesis for $(k-2)$ to lower bound the contribution of the non-global points. We construct a new line metric, $M^{\prime }$ by taking a non-global point from every interval containing a non-global point. There are at $n^{\prime }=\frac{n}{{\mathrm{\ell }}_i}$ intervals and at least $p^{\prime }=(1-{\gamma }_i)\frac{n}{{\mathrm{\ell }}_i}$ of them contain a non-global point. Interconnecting the points in $M^{\prime }$ contributes at least $W_{k-2}(p^{\prime },n^{\prime })$ to the total weight of $H_k$. The total weight of $H_k$ can be lower bounded as follows.

Using that $p\le n$, we have $ck{n}^{2/k}\ge ck{\left(p^2/n\right)}^{2/k}$, as required.

Finally, we consider the cases $i^{\prime }$.1 and $i^{\prime }$.2, where $i^{\prime }=\lfloor {\log }_{32}(ek)\rfloor$.

Observe that ${\gamma }_{i^{\prime }}\ge \frac{1}{2}-\frac{1}{3}=\frac{1}{6}$, since ${\gamma }_0\ge \frac{1}{2}$ and for every $1\le i\le i^{\prime }$ it holds that ${\gamma }_i>{\gamma }_{i-1}-\frac{1}{4^i}$. By Claim 22, the contribution of the global points is at least ${\gamma }_{i^{\prime }}^2{\mathrm{\ell }}_{i^{\prime }}/16$, which can be lower bounded as follows.