# Routing Schemes and Distance Oracles in the Hybrid Model

Fabian Kuhn and Philipp Schneider<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

The $\mathsf{HYBRID}$ model was introduced as a means for theoretical study of
distributed networks that use various communication modes. Conceptually, it is
a synchronous message passing model with a local communication mode, where in
each round each node can send large messages to all its neighbors in a local
network (a graph), and a global communication mode, where each node is
allotted limited (polylogarithmic) bandwidth per round which it can use to
communicate with any node in the network.

Prior work has often focused on shortest paths problems in the local network,
as their global nature makes these an interesting case study how combining
communication modes in the $\mathsf{HYBRID}$ model can overcome the individual
lower bounds of either mode. In this work we consider a similar problem,
namely computation of distance oracles and routing schemes. In the former, all
nodes have to compute local tables, which allows them to look up the distance
(estimates) to any target node in the local network when provided with the
label of the target. In the latter, it suffices that nodes give the next node
on an (approximately) shortest path to the target.

Our goal is to compute these local tables as fast as possible with labels as
small as possible. We show that this can be done exactly in
$\widetilde{O}(n^{1/3})$ communication rounds and labels of size
$\Theta(n^{2/3})$ bits. For constant stretch approximations we achieve labels
of size $O(\log n)$ in the same time. Further, as our main technical
contribution, we provide computational lower bounds for a variety of problem
parameters. For instance, we show that computing solutions with stretch below
a certain constant takes $\widetilde{\Omega}(n^{1/3})$ rounds even for labels
of size $O(n^{2/3})$.

##  1\. Introduction

#### Hybrid Networks

Real networks often employ multiple communication modes. For instance, mobile
devices combine high-bandwidth, short-range wireless communication with
relatively low-bandwidth cellular communication (c.f., 5G [8]). Other examples
are hybrid data centers, which combine wireless and wired communication [16]
or optical circuit switching and electrical packet switching [33], or software
defined networking [32].

In this article we utilize the theoretical abstraction of such hybrid
communication networks provided by [5] which became known as hybrid model and
was designed to reflect a high-bandwidth local communication mode and a low-
bandwidth global communication mode, capturing one of the main aspects of real
hybrid networks. Fundamentally, the hybrid model builds on the concept of
synchronous message passing, a classic model to investigate communication
complexity in distributed systems.

###### Definition 1.1 (Synchronous Message Passing, c.f., [23]).

Let $V$ be a set of $n$ nodes with unique identifiers
$ID)(\cdot):V\to[n]$.111$[k]:=\\{1,\ldots,k\\}$ for $k\in\mathbb{N}$. Time is
slotted into discrete rounds consisting of the following steps. First, all
nodes receive the set of messages addressed to them in the last round. Second,
nodes conduct computations based on their current state and the set of
received messages to compute their new state (randomized algorithms also
include the result of some random function). Third, based on the new state the
next set of messages is sent.

Synchronous message passing has a clear focus on investigating communication
complexity, i.e., the number of communication rounds required to solve a
problem with an input distributed over all nodes (usually a graph problem).
For this purpose, nodes are usually assumed to be computationally
unbounded.222Occasionally this model is “overexploited”, e.g., nodes are
supposed solve $\mathcal{NP}$-complete problems on their local data. We will
refrain from that. The hybrid model then places additional restrictions on the
messages size and which pairs of nodes can exchange them.

###### Definition 1.2 (Hybrid model [5]).

The $\mathsf{HYBRID}(\lambda,\gamma)$ model is a synchronous message passing
model (Def. 1.1), subject to the following restrictions. _Local mode:_ nodes
may send one message per round of maximum size $\lambda$ bits to each of their
neighbors in a graph. _Global mode:_ nodes can send and receive messages of
total size at most $\gamma$ bits per round to/from any other node(s) in the
network. If the restrictions are not adhered to then a strong adversary333The
strong adversary knows the states of all nodes, their source codes and even
the outcome of all random functions. selects the messages that are delivered.

Note that the parameter spectrum of the $\mathsf{HYBRID}(\lambda,\gamma)$
model covers the standard models $\mathsf{LOCAL}$, $\mathsf{CONGEST}$,
$\mathsf{CLIQUE}$ (aka “Congested Clique”) and $\mathsf{NCC}$ (“Node
Capacitated Clique”) as marginal cases.444$\mathsf{LOCAL}$:
$\lambda\\!=\\!\infty,\gamma\\!=\\!0$, $\mathsf{CONGEST}$:
$\lambda\\!=\\!\smash{O}(\log n),\gamma\\!=\\!0$, $\mathsf{CLIQUE}$ (+
Lenzen’s Routing scheme [19]): $\lambda\\!=\\!0,\gamma\\!=\\!n\log n$,
$\mathsf{NCC}$: $\lambda\\!=\\!0,\gamma\\!=\\!\smash{O}(\log^{2}n)$. Given the
ramifications of investigating $\mathsf{HYBRID}(\lambda,\gamma)$ in its
entirety, we narrow our scope (for our upper bounds) to a particular
parametrization that pushes both communication modes to one extreme end of the
spectrum. Following the argumentation of [5] we leave the size of local
messages unrestricted (modeling high local bandwidth) and allow only
$\operatorname{polylog}n$ bits of global communication per node per round
(modeling severely restricted global bandwidth). Formally, we define the
“standard” hybrid model as combination of the standard $\mathsf{LOCAL}$ and
$\mathsf{NCC}$ [4] models:
$\mathsf{HYBRID}:=\mathsf{HYBRID}\big{(}\infty,\smash{O}(\log^{2}n)\big{)}$.555Choosing
$\gamma=\smash{O}(\log^{2}n)$ is due to convenience. It allows nodes to
exchange $\smash{O}(\log n)$ global messages of size $\smash{O}(\log n)$ bits,
which often makes randomized algorithms more concise. The slight arbitrariness
of this choice is one reason to resort to the $\smash{\widetilde{O}}$ notation
for analyzing the round complexity. Note that our lower bounds are
parametrized for the more general $\mathsf{HYBRID}(\infty,\gamma)$ model
(which also yields lower bounds for the weaker $\mathsf{HYBRID}$ model).

#### Routing Schemes & Distance Oracles

A fundamental aspect of the Internet Protocol is packet forwarding, where
every node has to compute a routing function, which – when combined with
target-specific information stored in the packet header – must indicate the
neighbor which the packet has to be forwarded to such that it reaches its
intended destination. A correct routing scheme consists of these routing
functions and a unique label per node, such that the packet forwarding
procedure induces a path in the network from any source node to any
destination node specified by the corresponding label attached to the packet.

Typically, a distinction is made between stateful and stateless routing
schemes. In the former, routing can be based on additional information
accumulated in the packet header as the packet is forwarded, whereas in the
latter routing decisions are completely oblivious to the previous routing
path. A related problem is the computation of distance oracles, which has some
similarities to the all pairs shortest paths problem. Each node must compute
an oracle function that provides the distance (or an estimate) to any other
node when provided with the corresponding label. Formal definitions are given
in Section 1.3 (Def. 1.3, 1.4 and 1.5).

Our first goal is to gather the necessary information for labels, routing and
oracle functions with as few communication rounds as possible. This is
particularly important for dynamic or unreliable networks where changes in
distances or topology necessitates (frequent) re-computation. In this work we
allow that node labels666Allowing relabeling is also called a labeling scheme.
may contain information that help with distance estimation and routing
decisions, which gives rise to our second goal; keeping node labels
small.777Usually the amount of information stored at nodes for routing and
distance estimation is also considered. Since the nodes in our model are
computationally unbounded we do not focus on that. Our lower bounds have also
no restriction on the local information. The third goal is to speed up the
actual packet forwarding process to minimize latency and alleviate congestion.
Given a graph with edge weights corresponding to (e.g.) link-latencies, we
want to minimize the largest detour any packet takes in relation to the
corresponding shortest path. This is also known as stretch. Analogously, for
distance oracles we want to minimize the worst estimation error relative to
the true distance.

#### Routing Schemes & Distance Oracles in Distributed Networks

In this work we are interested solving the above problems in a distributed
setting (c.f., Definition 1.1). This has particular importance given the
distributed nature of many real networks where routing problems are relevant
(most prominently, the Internet) and where providing a centralized view of the
whole network is prohibitively expensive. Note that we are interested in
computing routing schemes and distance oracles for the local communication
network, which is motivated by the fact that typically lots of packets are
routed during an ongoing session and due bandwidth and cost constraints of the
global mode. However, the global mode can be used to send the (relatively
small) destination label to the source of a packet quickly, which can then be
stored at that node for the duration of a session.

From an algorithmic standpoint, computing routing schemes and distance oracles
is an inherently global problem. That is, allowing only local communication
(i.e., the $\mathsf{LOCAL}$ model) it takes $\Omega(n)$ rounds to accomplish
this (we provide a proof of this in Lemma D.1).888Any graph problem can be
solved in $\smash{O}(n)$ rounds in $\mathsf{LOCAL}$ by collecting the graph
and solving the problem locally at some node. This makes global problems
uninteresting for the $\mathsf{LOCAL}$ model, unless communication
restrictions are increased (c.f., $\mathsf{CONGEST}$) or decreased (c.f.,
$\mathsf{HYBRID}$). A similar observation can be made for the global
communication mode ($\mathsf{NCC}$ model). If we are only allowed to use
global communication and each node initially only knows its incident edges in
the local network, it takes $\smash{\widetilde{\Omega}}(n)$999The
$\smash{\widetilde{O}}(\cdot)$ notation suppresses multiplicative terms that
are polylogarithmic in $n$. rounds to compute routing schemes and distance
oracles (we show that in Lemma D.2).101010Computing routing schemes in
$\mathsf{NCC}$ is somewhat artificial, as the need for routing schemes for a
local network suggests that it exists and can be used. This article addresses
the question whether the combination of the two communication modes in the
$\mathsf{HYBRID}$ model can overcome the $\smash{\widetilde{\Omega}}(n)$ lower
bound of the individual modes $\mathsf{LOCAL}$ and $\mathsf{NCC}$.

Our answer to this is two-pronged. First we show that indeed, we can compute
routing schemes and distance oracles significantly faster, for instance, we
show $\smash{\widetilde{O}}(n^{1/3})$ rounds and labels of size
$\Theta(n^{2/3})$ suffice (c.f., Theorem 2.5). Second, we show that the
$\mathsf{HYBRID}$ model is not arbitrarily powerful by giving polynomial lower
bounds for these problems (depending on the stretch) that hold even for
relatively large labels and unbounded local memory. For instance, we show that
it takes $\smash{\widetilde{\Omega}}(n^{1/3})$ rounds to solve either problem
exact, even for unweighted graphs and labels of size $\smash{O}(n^{2/3})$
(c.f., Theorem 4.3). We provide numerous, more nuanced results, depending on
stretch and the type of problem, summarized in the following.

###  1.1. Contributions and Overview

Our contributions and results are summarized in Table 1, which gives a
simplified overview of our complexity results for the various forms of routing
scheme and distance oracle problems. Here we also want to give some intuition
into how our techniques work and highlight how some of the results are
generalized in the main part.

problem | stretch | complexity | label-size | reference
---|---|---|---|---
distance oracles | $3\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/3})$ | $\smash{O}(n^{2/3})^{\dagger}$ | Thm. 5.6
$\ell$ | $\smash{\widetilde{\Omega}}\big{(}n^{1/f(\ell)}\big{)}^{\ddagger}$ | $\smash{O}\big{(}n^{2/f(\ell)}\big{)}^{\ddagger}$ | Thm. 5.6, 5.7
stateless routing schemes | $\sqrt{3}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/3})$ | $\smash{O}(n^{2/3})^{\dagger}$ | Thm. 5.9
$\sqrt{5}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/5})$ | $\smash{O}(n^{2/5})^{\dagger}$ | Thm. 5.9
$1\\!+\\!\sqrt{2}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/7})$ | $\smash{O}(n^{2/7})^{\dagger}$ | Thm. 5.9
stateful routing schemes | $\sqrt{2}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/3})$ | $\smash{O}(n^{2/3})^{\dagger}$ | Thm. 5.11
$\frac{5}{3}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/5})$ | $\smash{O}(n^{2/5})^{\dagger}$ | Thm. 5.11
$\frac{7}{4}\\!-\\!\varepsilon$ | $\smash{\widetilde{\Omega}}(n^{1/7})$ | $\smash{O}(n^{2/7})^{\dagger}$ | Thm. 5.11
$\approx 1.78$ | $\smash{\widetilde{\Omega}}(n^{1/11})$ | $\smash{O}(n^{2/11})$ | Thm. 5.11
all on unw. graphs | exact | $\smash{\widetilde{\Omega}}(n^{1/3})$ | $\smash{O}(n^{2/3})^{\dagger}$ | Thm. 4.3
$1\\!+\\!\varepsilon$ | $\smash{\widetilde{O}}(n^{1/3}/\varepsilon)$ | $\Theta(\log n)$ | Thm. 2.9
all on weigh. graphs | exact | $\smash{\widetilde{O}}(n^{1/3})$ | $\Theta(n^{2/3})$ | Thm. 2.5
3 | $\smash{\widetilde{O}}(n^{1/3})$ | $\Theta(\log n)$ | Thm. 2.9

  * •

$\dagger$ The lower bound on round complexity holds any node labeling of at
most that size.

  * •

$\ddagger$ For some function $f(\ell)$ that is linear in $\ell$.

Table 1. Selected and simplified contributions of this paper.

#### Lower Bounds Summary

Our main contribution revolves around computational lower bounds for computing
distance oracles and stateless and stateful routing schemes in the
$\mathsf{HYBRID}$ model. Lower bounds for approximations are summarized in the
first three groups of Table 1. We also provide a lower bound on unweighted
graphs, given in the first row of the fourth group of Table 1. Note that all
lower bounds hold regardless of the allowed local memory. Moreover, our lower
bounds hold for randomized algorithms with constant success probability.

In the main part, our results are formulated for the more general
$\mathsf{HYBRID}(\infty,\gamma)$ model, that is $\gamma$ appears as a
parameter. For instance, our lower bound on unweighted graphs is in fact
$\Omega(n^{1/3}/\gamma^{1/3})$ rounds for labels of size up to $c\cdot
n^{2/3}\cdot\gamma^{1/3}$ for some $c>0$ (c.f., Theorem 4.3), that is, we get
a polynomial lower bound for the $\mathsf{HYBRID}(\infty,\gamma)$ model for
any $\gamma\in\tilde{o}(n)$. For easier readability we plug in the “standard”
$\mathsf{HYBRID}$ model with $\gamma=\smash{\widetilde{O}}(1)$, which lets us
hide $\gamma$ by using the $\smash{\widetilde{\Omega}}$ notation.

#### Lower Bounds Overview

The general proof idea is based on information theory and plays out roughly as
follows. We start out with a two party communication problem, where Alice is
given the state of some random variable $X$ and needs to communicate it to Bob
(c.f., Definition 3.2). Any communication protocol that achieves this needs to
communicate $H(X)$ (Shannon entropy of $X$ [25]) bits in expectation (c.f.,
Corollary B.2), which is a consequence of the source coding theorem
(replicated in Lemma B.1).

In Section 3 we translate this to the $\mathsf{HYBRID}$ setting into what we
call the node communication problem. There, we have two sets of nodes $A$ and
$B$, where nodes in $A$ “collectively know” the state of some random variable
$X$ and need to communicate it to $B$ (for more precise information see
Definition 3.1). We show a reduction (via a simulation argument) where a
$\mathsf{HYBRID}$ algorithm that solves the node communication problem on sets
$A$ and $B$ that are at sufficiently large distance in the local graph, can be
used to derive a protocol for the two party communication problem (c.f., Lemma
3.3). We conclude that for sets $A,B$ with distance at least $h$ it takes
$\smash{\widetilde{\Omega}}\big{(}\min(H(X)/n,h)\big{)}$ rounds to solve this
problem (Theorem 3.4).

In Section 4 we give a reduction from the node communication problem to
distance oracle and routing scheme computation. The goal is to encode some
random variable $X$ with large entropy (super-linear in $n$) into some
randomized part of our local communication graph such that some node set $A$
knows $X$ by vicinity. We construct such a graph $\Gamma$ (see Figure 1) from
the complete bipartite graph $G_{k,k}=(A,E)$ and a (i.i.d.) random
$k^{2}$-bit-string $X=(x_{e})_{e\in E}$ with $H(X)=\Theta(k^{2})$. Then an
edge $e\in E$ of $G_{k,k}$ is present in $\Gamma$ iff $x_{e}=1$.

The nodes in $A$ collectively know $X$ since they are incident to the edges
sampled from $G_{k,k}$. We designate $k$ nodes of $A$ (one side of the
bipartition in $G_{k,k}$) as the “target nodes”. Then we connect each target
with a path of length $h$ to one of $k$ “source nodes” which will take the
role of $B$ (see Figure 1). We show that if the nodes in $B$ learn the
distances to the source nodes they also learn about the (non-)existence of the
edges sampled from $G_{k,k}$ and can conclude the state of $X$ and thus have
solved the node communication problem. Choosing the trade-off between $k$ and
$h$ appropriately (roughly $n^{2/3}$ and $n^{1/3}$) we conclude
$\smash{\widetilde{\Omega}}\big{(}\min(H(X)/n,h)\big{)}=\smash{\widetilde{\Omega}}(n^{1/3})$
rounds of communication must have taken place to solve the (exact) distance
oracle problem (Theorem 4.3).

One caveat is that in the distance oracle problem the nodes are only supposed
to give a distance to a target when also provided with the target-label. So we
choose the labels sufficiently small such that the “free information”, given
in form of the labels of all targets, is negligible. We can allow labels of
size $\smash{O}(n^{2/3})$ without changing the above narrative, see Theorem
4.3. For routing schemes we have to adapt the graph $\Gamma$ a bit. We add a
slightly longer alternative route from sources to targets (Figure 1, left
side) and show that the existence of edges and thus the state of $X$ can be
concluded from the first routing decision the sources have to make.

So far we got lower bounds only for exact solutions with the advantage that
they hold on unweighted graphs. In Section 5 we show how to use graph weights
to get lower bounds for approximation algorithms. For this we replace
$G_{k,k}$ with a balanced, bipartite graph $G=(A,E)$ with $k$ nodes and girth
$\ell$ (length of the shortest cycle in $G$). As before, the existence of an
edge $e\in E$ in $\Gamma$ is determined by to a random bit string
$X=(x_{e})_{e\in E}$, c.f., Figure 2. If some edge $e\in E$ is not in
$\Gamma$, then the detour in $\Gamma$ between the endpoints of $e$ is at least
$\ell\\!-\\!1$ edges (otherwise $e$ closes a loop of less than $\ell$ edges).
By assigning large weights to edges sampled from $G$, we can transform this
into multiplicative detour of almost $\ell\\!-\\!1$. Similar to the idea in
the unweighted case, any algorithm for distance oracles that has stretch
slightly smaller than $\ell\\!-\\!1$ can be used to solve the node
communication problem, which takes
$\smash{\widetilde{\Omega}}\big{(}\min(H(X)/n,h)\big{)}$ rounds.

To optimize the lower bound we need to maximize the entropy $H(X)$ of
$X=(x_{e})_{e\in E}$, i.e., the density of $G$. However, it is well known that
girth and density of a graph are opposing goals: a graph with girth $2g+1$ can
have at most $\smash{O}\big{(}n^{1+1/g}\big{)}$ edges (c.f., [6], simplified
in Lemma C.2). This inherently limits the amount of information we can encode
in $\Gamma$ and we show in Lemma 5.4 how graph density affects lower bounds
for the node communication problem. The good news is, that for some girth
values, graphs that achieve their theoretical density limit actually exist and
have been constructed (c.f., 9, 27, simplified form given in Lemma C.3). For
higher girth values, graphs that come close to that limit are known (c.f.,
[22], simplified form in Lemma C.4).111111There is a long standing conjecture
that for each girth $2g\\!+\\!1$ there exists a graph that reaches the
theoretical limit of $\smash{O}\big{(}n^{1+1/g}\big{)}$ edges ([14], c.f.,
Conjecture C.1). Our tools can be used to generate new lower bounds in case
new such graphs are found.

Utilizing these graphs we achieve polynomial lower bounds for the distance
oracle problem for some small stretch values (c.f., Theorem 5.6) and for
arbitrary constant stretch (c.f., Theorem 5.7). Theorem 5.7 is heavily
parametrized, but to sum it up in a simpler way: for any constant stretch
$\ell$ we attain a polynomial lower bound of
$\smash{\widetilde{\Omega}}(n^{1/f(\ell)})$, that is, $f(\ell)$ is constant as
well (roughly $f(\ell)\approx\frac{3}{2}\ell$).

For approximate routing schemes we have to be more careful and also make a
distinction between the stateless and stateful variant (c.f., Definitions 1.4,
1.5). The idea is the same as in the exact, unweighted case, however, since a
wrong routing decision at the source can still be completed into a routing
path of relatively good quality, the best stretch that can be achieved for
lower bounds is limited (even more so for stateful routing, where a packet may
“backtrack”). In particular, allowing too much stretch can open up unwanted
routing paths that mislead the sources in their conclusions about $X$. We
forbid these unwanted routing paths using inequalities parametrized by the
stretch and graph weights. Maximizing the stretch subject to these conditions
we obtain the lower bounds for stretch values that are given in the second and
third group of Table 1 with details in Theorems 5.9 and 5.11.

#### Upper Bounds Summary & Overview

Our computational upper bounds (Given in Appendix 2) can be expressed more
concisely due to the existence of efficient randomized algorithms for shortest
path problems in the $\mathsf{HYBRID}$ model. In particular we draw on fast
solutions for the so called random sources shortest paths problem (RSSP) [11],
where all nodes must learn their distance to a set of i.i.d. randomly sampled
nodes, say $S$. After solving RSSP, our strategy is to use the distance
between a node $u$ and the nodes in $S$ as its label $\lambda(u)$.

Roughly speaking, provided that $u$ is sufficiently “far away”, a node $v$ can
combine $\lambda(u)$ with its own distances to $S$ to compute its distance
(estimate) to $u$. If $u$ is “close” then we can use the local network to
compute the distance directly. While this gives us only distance oracles, it
is relatively straight forward to also derive routing schemes. Simply
speaking, we can always send a packet to a neighbor that has the best distance
(estimate) to $u$ (some care must be taken for approximations). Note that this
process is oblivious to previous routing decisions so the obtained routing
scheme is stateless (c.f., Definition 1.4).

A trade-off arises from the local exploration around nodes and the global
computation depending on the size of $S$ (since we solve RSSP on $S$), which
balances out to a round complexity of $\smash{\widetilde{O}}(n^{1/3})$ with
$|S|\in\smash{\widetilde{O}}(n^{2/3})$ (similar trade-offs were observed for
shortest paths problems in [5, 18, 11]). For exact algorithms (distance
oracles and routing schemes) we require labels of size $\Theta(n^{2/3})$
(however we can decrease the label size to $\Theta(n^{2/3-\zeta})$ at a cost
of $\smash{\widetilde{O}}(n^{1/3+\zeta})$ rounds, c.f., Theorem 2.5). This is
tight up to $\operatorname{polylog}n$ factors as is shown by the corresponding
lower bound in Table 1 group 4 line 1 (which holds even on unweighted graphs).

For smaller labels we show that restricting $\lambda(u)$ to $u$’s closest node
in $S$ gives good approximations. We obtain a 3-approximation on weighted
graphs and a $(1\\!+\\!\varepsilon)$ approximation on unweighted graphs in
$\smash{\widetilde{O}}(n^{1/3})$ rounds (assuming $\varepsilon>0$ is constant)
with labels of size $\smash{O}(\log n)$ (c.f., Theorem 2.9). Compare this to
our lower bounds: even much larger labels of size $\Theta(n^{2/3})$ do not
help to improve the runtime or the stretch by much, as this still takes
$\smash{\widetilde{\Omega}}(n^{1/3})$ rounds for stretch of
$3\\!-\\!\varepsilon$ for distance oracles on weighted graphs, and stretch $1$
on unweighted graphs (see Table 1).

###  1.2. Related Work

There was an early effort to approach hybrid networks from a theoretic angle
[7], with a conceptually different model.121212Essentially [7] combines
$\mathsf{LOCAL}$ with a global channel where in each round one node may
broadcast a message, making it much weaker than the $\mathsf{HYBRID}$ model.
Research on the current take of the $\mathsf{HYBRID}$ model was initiated by
[5] in the context of shortest paths problems, which most of the research has
focused on so far. As shortest paths problems problems are closely related, we
give a brief account of the recent developments.

#### Shortest Paths in the Hybrid Model

[5] introduced an information dissemination scheme to efficiently broadcast
small messages to all nodes in the network. Using this protocol, they derive
various solutions for shortest paths problems. For instance, for SSSP:131313In
the $k$ sources shortest paths problem ($k$-SSP) all nodes must learn their
distance to $k$ dedicated source nodes. Then SSSP
$\stackrel{{\scriptstyle\text{def}}}{{=}}$ $1$-SSP, APSP
$\stackrel{{\scriptstyle\text{def}}}{{=}}$ $n$-SSP. a $(1\\!+\\!\varepsilon)$
stretch, $\smash{\widetilde{O}}(n^{1/3})$-round algorithm and a
$(1/\varepsilon)^{\smash{O}(1/\varepsilon)}$-stretch,
$\smash{\widetilde{O}}(n^{\varepsilon})$-round algorithm.141414[5] also gives
an exact, $\smash{\widetilde{O}}\big{(}\\!\sqrt{\text{SPD}}\big{)}$-round SSSP
algorithm depending on the shortest path diameter SPD, using a completely
different approach. Further, an approximation of APSP with stretch 3 in
$\smash{\widetilde{O}}(n^{1/2})$ rounds, which closely matches their
corresponding $\smash{\widetilde{\Omega}}(n^{1/2})$ lower bound (which holds
for much larger stretch). Subsequently, [18] introduced a protocol for
efficient routing of small messages between dedicated source-target pairs in
the $\mathsf{HYBRID}$ model (not to be confused with routing schemes), which
they use to solve APSP and SSSP exactly in $\smash{\widetilde{O}}(n^{1/2})$
and $\smash{\widetilde{O}}(n^{2/5})$ rounds, respectively. For computing the
diameter they provide algorithms (e.g., a $3/2\\!+\\!\varepsilon$
approximation in $\smash{\widetilde{O}}(n^{1/3})$ rounds) and a
$\smash{\widetilde{\Omega}}(n^{1/3})$ lower bound. [11] combines the
techniques of [18] with a densitiy sensitive approach, to solve $n^{1/3}$-SSP
(thus SSSP) exactly and compute a $(1\\!+\\!\varepsilon)$-approximation of the
diameter in $\smash{\widetilde{O}}(n^{1/3})$ rounds.151515As we reuse some
techniques of [5, 18, 11], we explain them in a bit more detail in Section 2).
[12] uses density awareness in a different way to improve SSSP to
$\smash{\widetilde{O}}(n^{5/17})$ rounds for a small stretch of
$(1\\!+\\!\varepsilon)$. [1] derandomized the dissemination protocol of [5] to
obtain a deterministic APSP-algorithm with stretch $\frac{\log n}{\log\log n}$
in $\smash{\widetilde{O}}(n^{1/2})$ rounds. For classes of sparse graphs
(e.g., cactus graphs) [15] demonstrates that $\operatorname{polylog}n$
solutions are possible even in the harsher hybrid combination
$\mathsf{CONGEST}$ and $\mathsf{NCC}$.

#### Routing Schemes in Distributed Models

Routing schemes in a hybrid network model have been pioneered in [10]. Their
work can be contrasted to this article in three main ways: First, they
consider specific types of local graphs, namely “hole-free” grid graphs and
unit disc graphs (UDGs) (which have practical relevance in the context of
wireless local networks), whereas this work focuses on general graphs. Second,
[10] provides upper bounds based on a routing scheme on a grid-graph
abstraction of UDGs, whereas the main technical contribution of this work are
lower bounds. Third, we consider hybrid networks with unlimited
$\mathsf{LOCAL}$ edges (which strengthens our lower bounds), whereas [10]
gives a $\smash{O}(\log n)$ round algorithm with labels and local tables of
size $\smash{O}(\log n)$ and stretch 1 and constant stretch on certain grid-
graphs and UDGs, respectively, which holds even for the stricter combination
of $\mathsf{CONGEST}$ and $\mathsf{NCC}$. Note that our lower bounds
supplement the work of [10] in that it shows the necessity to narrow the scope
(for instance to particular graph classes) in order to achieve $\smash{O}(\log
n)$ round algorithms with small labels and stretch.

A related line of work investigates the round complexity of implementing
routing schemes and distance oracles in the $\mathsf{CONGEST}$ model, where
the challenge is that only small local messages can be used. Here, a
$\smash{\widetilde{\Omega}}(n^{1/2}\\!+\\!D_{G})$ lower bound for computing
routing schemes is implied by [26] (even for polynomial labels, whereas
$D_{G}$ is the diameter of $G$). For distance oracles in $\mathsf{CONGEST}$,
[17] gives a lower bound of $\Omega(n^{\frac{1}{2}+\frac{1}{5k}})$ with
stretch $2k$ for graphs with small diameter assuming Erdős’ girth conjecture
(c.f., Conjecture C.1). Their bound holds for small labels without this
assumption. A line of papers narrows the gap to these lower bounds [20, 21,
13]. For instance [13] achieves a routing scheme with stretch $\smash{O}(k)$,
routing tables of size $\smash{\widetilde{O}}(n^{1/k})$, labels of size
$\smash{\widetilde{O}}(k)$ in
$\smash{O}\big{(}n^{1/2+1/k}\\!+\\!D_{G}\big{)}\cdot n^{o(1)}$ rounds.

#### Routing Schemes as Distributed Data Structure

In this branch of research the goal is often to optimize the trade-off between
stretch and the size of the local routing tables. It is well established that
$\smash{\widetilde{O}}(n)$ bit of memory per node always suffices for routing
schemes161616As $\smash{\widetilde{O}}(n)$ bit of memory allows each node to
store the next node for every destination. [24]. For routing schemes on
general graphs with small stretch ($<\\!3$) $\Omega(n)$ bit are required [24,
29].171717With $o(n)$ local memory a $\Omega(n)$-degree node has to “forget”
neighbors, necessarily generating a detour when routing to the neighbors that
have been forgotten. This lower bound is part of the reason why we do not
analyze local memory in this work. More generally, for a stretch smaller than
$2k\\!+\\!1$ it is known that local tables of size $\Omega({n^{1/k}})$ bit are
required for small values $k\in\\{1,2,3,5\\}$, see [29]. This is true for all
parameters of $k$ if one believes Erdős’ girth conjecture (see Conjecture C.1)
[29]. The reliance on this conjecture can be dropped for weaker name-
independent routing schemes, where nodes can not be re-labeled and [2] shows
that this requires $\Omega({(n\log n)^{1/k}})$ memory for any stretch smaller
than $2k\\!+\\!1$. On the positive side, [29] shows that a stretch of
$\smash{O}(k)$ with $\smash{\widetilde{O}}({kn^{1/k}})$ memory can be
achieved. The concrete stretch is $4k\\!-\\!5$ or even $2k\\!-\\!1$ (i.e.,
almost optimal) if handshaking is allowed (an initial exchange of a message
between source and destination before a packet is routed). The lower bound for
name independent routing has been contrasted with a scheme that achieves
$O(k)$ stretch with memory size $\smash{\widetilde{O}}(k^{2}n^{1/k})$ [3].

###  1.3. Preliminaries

#### General Definitions

The scope of this paper is solving graph problems, typically in the undirected
communication graph. Let $G=(V,E)$ be undirected. Edges have weights
$w:E\to[W]$, where $W$ is at most polynomial in $n$, thus the weight of an
edge and of a simple path fits into a $\smash{O}(\log n)$ bit message.181818In
this article, $\log$ functions are always to the base of 2. A graph is
considered unweighted if $W=1$. Let $w(P)=\sum_{e\in P}w(e)$ denote the length
of a path $P\subseteq E$. Then the _distance_ between two nodes $u,v\in V$ is

$d_{G}(u,v):=\\!\min_{\text{$u$-$v$-path }P}w(P).$

A path with smallest length between two nodes is called a _shortest path_. Let
$|P|$ be the number of edges (or _hops_) of a path $P$. The _hop-distance_
between two nodes $u$ and $v$ is defined as:

$\operatorname{hop}_{G}(u,v):=\\!\min_{\text{$u$-$v$-path
}P}|P|.\vspace*{-1mm}$

We generalize this for sets $U,W\subseteq V$ (whereas
$\operatorname{hop}_{G}(v,v):=0$):

$\operatorname{hop}_{G}(U,W):=\\!\min_{u\in U,w\in
W}\operatorname{hop}_{G}(u,w).\vspace*{-1mm}$

The _diameter_ of $G$ is defined as:

$D_{G}:=\max_{u,v\in V}\operatorname{hop}_{G}(u,v).$

Let the _$h$ -hop distance_ from $u$ to $v$ be:

$d_{G,h}(u,v):=\\!\\!\min_{{\text{$u$-$v$-path }P,|P|\leq h}}\,w(P).$

If there is no $u$-$v$ path $P$ with $|P|\leq h$ we define
$d_{h}(u,v):=\infty$. We drop the subscript $G$, when $G$ is clear from the
context. In this paper we consider the following problem types:

###### Definition 1.3 (Distance Oracles).

Every node $v\in V$ of a graph $G=(V,E)$ needs to compute a label $\lambda(v)$
and an oracle function $o_{v}:\lambda(V)\to\mathbb{N}$, such that
$o_{v}(\lambda(u))\geq d(u,v)$ for all $u\in V$. An oracle function $o_{v}$ is
an $(\alpha,\beta)$-approximation if $o_{v}(\lambda(u))\leq\alpha\cdot
d(u,v)+\beta$ for all $u,v\in V$, that is, $\alpha,\beta$ are the
multiplicative and additive approximation error, respectively. We speak of a
stretch of $\alpha$ in case of an $(\alpha,0)$-approximation. If the stretch
is one, we call $o_{v}$ exact.

###### Definition 1.4 (Stateless Routing Scheme).

Every node $v\in V$ of a graph $G=(V,E)$ needs to learn a label $\lambda(v)$
and a routing function (sometimes called “table”) $\rho_{v}:\lambda(V)\to
N(v)\cup\\{v\\}$ where $N(v)$ are adjacent nodes of $v$ in $G$ (whereas we
formally set $\rho_{v}(\lambda(v)):=v$). The functions $\rho_{v}$ must fulfill
the following correctness condition. Let $v_{0}:=v$ and recursively define
$v_{i}:=\rho_{v_{i-1}}(\lambda(u))$. Then the routing functions $\rho_{v},v\in
V$ must satisfy $v_{h}=u$ for some $h\in\mathbb{N}$. Let $P_{\rho}(u,v)$ be
the path induced by the visited nodes $v_{0},\dots,v_{h}$. We call $\rho$ an
$(\alpha,\beta)$-approximation if $w(P_{\rho}(u,v))\leq\alpha d(u,v)+\beta$
for all $u,v\in V$.

###### Definition 1.5 (Stateful Routing Scheme).

This is mostly defined as in the stateless case, with the difference that the
routing function $\rho_{v}$ can additionally depend on the information
gathered along the path that has already been visited by a packet (which would
be stored in its header). Note that in this means that the routing path
defined by such a function $\rho$ is not necessarily simple (i.e., might have
loops).

###### Definition 1.6 (Randomized Graph Algorithms).

We say that an algorithm has success probability $p$, if it succeeds with
probability at least $p$ on every possible input graph (however, some of our
results are restricted to unweighted graphs as input). Specifically, for our
upper bounds we aim for success with high probability (w.h.p.), which means
with success probability at least $1-\frac{1}{n^{c}}$ for any constant $c>0$.

##  2\. Upper Bounds

The first part of this paper is to derive algorithms that compute routing
schemes and distance oracles in the $\mathsf{HYBRID}$ model, which we consider
as a warm-up and complementary to the subsequent section on lower bounds. We
can draw on the techniques and fast algorithms for shortest paths problems
from [5, 18, 11] (where most of the heavy lifting occurs) and show how to
leverage these to obtain distance oracles and routing schemes efficiently in
the $\mathsf{HYBRID}$ model. We start with a quick introduction to the
techniques we use.

###  2.1. Techniques

Skeleton graphs were first used by [30] and became one of the main tools used
in the context of shortest path algorithms in the $\mathsf{HYBRID}$ model
(c.f., [5, 18, 11]). Simply speaking, a skeleton is a minor of a graph $G$
consisting of a (usually relatively small) set of nodes sampled with some
probability $\frac{1}{x}$ and virtual edges formed between sampled nodes at
most $\smash{\widetilde{O}}(x)$ hops apart with weights such that distances in
the skeleton graph correspond to those in $G$ w.h.p.

The usual approach is to solve a given shortest path problem on an
appropriately sized skeleton graph by leveraging the global communication
provided by the $\mathsf{HYBRID}$ model and then extend that solution to the
whole graph using local communication. While at this point it is not necessary
to fully characterize skeleton graphs anymore (we use existing algorithms out
of the box), we still have to use the subsequent property for a random
sampling of nodes (from which all required properties of a skeleton graph are
derived).

Assume each node joins some set $S\subseteq V$ independently and identically
distributed (i.i.d.) with probability $1/x$ for some $x>1$. The expected
number of nodes joining $S$ is $\mathbb{E}(|S|)=n/x$, and we also have
$|S|\in\Theta(n/x)$ w.h.p. if $\mathbb{E}(|S|)$ is sufficiently large (which a
simple application of the Chernoff bound given in Lemma A.1 shows).
Furthermore, there exists some $h\in\smash{\widetilde{O}}(x)$ such that for
any $u,v\in V$ there will be a sampled node on some shortest $u$-$v$-path $P$
at least every $h$ hops for any $u,v\in V$ w.h.p. This is formalized as
follows (the proof can be found at the end of Appendix A).

###### Lemma 2.1 (c.f., [18], [5]).

Let $G=(V,E)$. Let each node join some set $S\subseteq V$ i.i.d. with
probability $\frac{1}{x}$. Then there is a constant $\xi\\!>\\!0$, such that
for any $u,v\\!\in\\!V$ with $hop(u,v)\\!\geq\\!h:=\xi x\ln n$, there is at
least one shortest path $P$ from $u$ to $v$, such that any sub-path $Q$ of $P$
with at least $h$ nodes contains a node in $S$ w.h.p.

We are interested in the distances to the sampled nodes, which can be
formalize as follows.

###### Definition 2.2 (Random Sources Shortest Paths (RSSP)).

Given a subset of nodes (sources) that were sampled i.i.d. with probability
$1/x$ for some $x\geq 1$ from an undirected, weighted graph $G$. The RSSP
problem is solved when every node in the network has learned its distance to
each of the random source nodes.

We provide a rough overview how RSSP was solved (simplified for $x=n^{1/3}$)
for readers unfamiliar with the topic. First, a skeleton graph of $G$ is
constructed on the $\Theta(n^{2/3})$ sampled nodes as in [5]. Note that edges
of that skeleton are at most $\smash{\widetilde{\Theta}}(n^{1/3})$ hops apart,
which means that one round of the $\mathsf{LOCAL}$ model can be simulated on
that skeleton graph in $\smash{\widetilde{\Theta}}(n^{1/3})$ real rounds.
Second, [18] showed that a round of the $\mathsf{CLIQUE}$ model191919In the
$\mathsf{CLIQUE}$ model, in each round each node is allowed to send a
(different) $\smash{O}(\log n)$ message to every node. can also be simulated
in $\smash{\widetilde{\Theta}}(n^{1/3})$ rounds on the skeleton graph using a
routing protocol tailored to the $\mathsf{HYBRID}$ model to efficiently
communicate $\smash{O}(\log n)$ bit messages between pairs of senders and
receivers.

Third, [11] observed that skeleton nodes with a high degree in the skeleton
graph can learn a lot of information by relying on the bandwidth of their
neighbors in the skeleton. With this observation they use
$\smash{\widetilde{O}}(1)$ simulated $\mathsf{LOCAL}$ and $\mathsf{CLIQUE}$
rounds (of $\smash{\widetilde{\Theta}}(n^{1/3})$ real rounds each) to compute
“tiered oracles” (not to be confused with distance oracles in this paper)
meaning that each node with a degree in a certain “tier” (exponential degree
class $\\{2^{i-1}\\!\\!\\!,\dots,2^{i}\\!-\\!1\\}$ with $i\in[\lceil\log
n\rceil]$) learns the subgraph of the skeleton graph induced by nodes of
degree in its own tier or below.

Iteratively, one can solve the all pairs shortest paths problem on the
skeleton. Initially, the nodes of the highest tier know the whole skeleton
graph and can send their distance to every node in one $\mathsf{CLIQUE}$
round. This information enables the nodes in the next lower tier to compute
their distance to every node in the skeleton. Then the process repeats (for
each of the $\smash{\widetilde{O}}(1)$ tiers) until eventually all pairs
shortest paths is solved on the skeleton. All other nodes in $G$ can learn
their distance to each skeleton node from those within
$\smash{\widetilde{O}}(n^{1/3})$ hops. The following lemma summarizes this.

###### Lemma 2.3 (c.f., [11]202020For our applications, it is convenient to
rephrase the result of [11], which considers sampling probabilities $n^{y-1}$
for $0<y<1$ with running time $\smash{\widetilde{O}}(n^{1/3}+n^{2y-1})$. This
corresponds to the variant given here via the substitution $y=1-\frac{\log
x}{\log n}$.).

There is an algorithm that solves the random sources shortest path problem for
sampling probability $1/x$ for some $x\geq 1$ exactly and w.h.p. in
$\smash{\widetilde{O}}(n^{1/3}+n/x^{2})$ rounds.

This result is almost tight (up to $\operatorname{polylog}(n)$ factors) for
$x=n^{1/3}$ (i.e., there are $|S|=\Theta(n^{2/3})$ sources) due to a
corresponding lower bound by [11] which was slightly adapted for random
sources from the $\smash{\widetilde{\Omega}}(\\!\sqrt{k})$ lower bound for the
$k$-sources shortest path problem given in [18].

###  2.2. Base Algorithm

We combine the previous two techniques to compute exact distance oracles and
routing schemes in the $\mathsf{HYBRID}$ model. We will presume a subroutine
explore($h$) that floods all graph information for $h$ hops such that
afterwards each node $u\in V$ knows $\mathcal{B}_{u,h}$ defined as the
subgraph induced by the nodes within $h$ hops around $u$. Furthermore we
presume a subroutine solve-rssp that solves RSSP on the sampled nodes in
accordance with Lemma 2.3.

Algorithm 1 gives an overview. The parameters $x$ and $h$ are tuning
parameters which will be specified for the task at hand. Algorithm 1 consists
of two parts: first all nodes collect the information required to compute
distance oracles and routing schemes. Second, in the last three lines, the
computation of the label $\lambda(v)$, oracle function $o_{v}$ and routing
function $\rho_{v}$ takes place (c.f., Definitions 1.3, 1.5). We will override
these sub-procedures to adapt the algorithm for exact and approximate results
and for the special case of unweighted graphs. The steps are described on a
node-level.

Algorithm 1 base-algorithm($x,h$) $\triangleright$ $h$ not smaller as in Lem.
2.1

$v$ joins $S$ with probability $\frac{1}{x}$

explore($h$) $\triangleright$ $v$ learns $\mathcal{B}_{v,h}$

solve-rssp $\triangleright$ with source nodes $S$

create-label $\triangleright$ computation of $v$’s problem-specific label

create-oracle-function $\triangleright$ output $o_{v}$ as in Def. 1.3

create-routing-function $\triangleright$ output $\rho_{v}$ as in Def. 1.4

###### Lemma 2.4.

Given that the last three lines have constant running time, Algorithm 1 takes
$\smash{\widetilde{O}}(n^{1/3}+n/x^{2}+h)$ rounds.

###### Proof.

The time consuming steps are explore($h$), i.e., the flooding of the graph for
$h\in\smash{\widetilde{\Omega}}(x)$ rounds and solving the RSSP with
$\smash{\widetilde{O}}(n^{1/3}+n/x^{2})$ (c.f., Lemma 2.3). ∎

###  2.3. Exact Distance Oracles & Routing Schemes

First, create-label computes $v$’s label
$\lambda(v):=\big{\\{}\big{(}\text{ID}(s),d(s,v)\big{)}\mid s\in S\big{\\}}$
corresponding to the identifiers of all nodes in $S$ and the associated
distances that are known from solving the RSSP problem. Second, for a given
label $\lambda(u)$ of some destination $u\in V$ create-oracle-function outputs
the following function

(1) $o_{v}(\lambda(u))=\min\Big{(}d_{h}(v,u),\,\min_{s\in
S}d(v,s)+d(s,u)\Big{)}$

Note that in the above equation we set $d(v,v)=0$ and $d_{h}(v,u)=\infty$ for
$u\notin\mathcal{B}_{v,h}$. The $h$-hop distances $d_{h}(v,u)$ are known since
$v$ knowns $\mathcal{B}_{v,h}$, the distances $d(v,s),s\in S$ are known from
solving the RSSP problem on $S$ and the distances between pairs $d(s,u),u\in
S$ are part of the label $\lambda(u)$, thus $o_{v}(\lambda(u))$ can be
computed by $v$.

Exchanging the computed distance oracles between neighbors problem gives us
sufficient information to solve the routing problem. Roughly speaking, the
next node on a shortest path is given by a neighbor that minimizes the
distance to the destination of the packet (a little bit of care has to be
taken for proving this, though).

More precisely, the subroutine create-routing-function will first do a single
round of communication so that each node $v$ learns the oracle function
$o_{w}$ of each of its neighbors $w$ in the local network. Then we use this
knowledge to pass the packet only to a neighbor whose distance oracle to the
target decreases by the weight of that edge (pick an arbitrary one if there is
more than one).

(2) $\displaystyle\rho_{v}(\lambda(u))\in\big{\\{}z\in N(v)\mid
o_{z}(\lambda(u))=o_{v}(\lambda(u))-w(v,z)\big{\\}}$

Note that additional knowledge of $o_{z}(\lambda(u))$ for $z\in N(v)$ is
sufficient to compute $\rho_{v}(\lambda(u))$. It remains to analyze the
resulting algorithm and give the remaining correctness arguments, which we do
in the proof of the following theorem. Note that here we obtain a trade off
between label size and the running time, which we formalize with a parameter
$\zeta$.

###### Theorem 2.5.

For any $\zeta\geq 0$ _exact_ distance oracles and _stateless_ routing schemes
with labels of size $\smash{O}(n^{\frac{2}{3}-\zeta})$ bits can be computed in
$\smash{\widetilde{O}}(n^{\frac{1}{3}+\zeta})$ rounds in the $\mathsf{HYBRID}$
model w.h.p.

###### Proof.

Note that for $\zeta\geq 2/3$ the problem becomes trivial (any graph problem
can be solved in $n$ rounds in $\mathsf{HYBRID}$), so we assume $\zeta<2/3$.
We choose $x=n^{\frac{1}{3}+\zeta}$ and $h=\smash{\widetilde{\Theta}}(x)$ as
in Lemma 2.1, then the runtime follows from Lemma 2.4. The number of sampled
nodes is $|S|\in\Theta(n^{\frac{2}{3}-\zeta})$ (a simple application of Lemma
A.1). As the label $\lambda(v)$ contains information of size $\smash{O}(\log
n)$ bits for each node $s\in S$ (recall that distances are polynomial in $n$),
$\lambda(v)$ requires $\smash{O}(n^{\frac{2}{3}-\zeta}\log n)$ bits. We can
shift the $\log n$ factor from the label size into the runtime (where it is
absorbed by the $\smash{\widetilde{O}}$ notation) with a substitution
$\zeta=\zeta^{\prime}+\frac{\log\log n}{\log n}$.

We already established in the algorithm description that the required
information to compute $\lambda(v)$, $o_{v}$ and $\rho_{v}$ is present at the
node $v$ from executing explore($h$) and solve-rssp. It remains to show that
$o_{v}(\lambda(u))=d(v,u)$. If there is a shortest $v$-$u$-path with at most
$h$ hops, then the first argument of the outer $\min$ function in Equation (1)
corresponds to $d(v,u)$. If all shortest $v$-$u$-paths have more than $h$ hops
then there must be a node $s\in S$ on one such path by Lemma 2.1, which means
that the second argument of the outer $\min$ function in Equation (1)
corresponds to $d(v,u)$.

Regarding the routing function, we observe that $z\in N(v)$ is the next node
on _some_ shortest path from $v$ to $u$ if and only if $d(v,u)=w(v,z)+d(z,u)$,
which is equivalent to $o_{z}(u)=o_{v}(u)-w(v,z)$ as $o_{v},o_{z}$ are exact
distance oracles. Since $G$ is connected, there is always a neighbor of $v$ on
some shortest path to $u$ so the set in Equation (2) is not empty. By always
choosing the next node on _some_ shortest path from the current node to $u$
(c.f., Equation (2)), we will naturally obtain a shortest $v$-$u$-path
overall. Note that the obtained routing scheme is oblivious to previous
routing decisions. ∎

###  2.4. Approximate Solutions

Note that if we do not want to compromise on the running time the label size
in Theorem 2.5 is $\smash{\widetilde{\Omega}}(n^{2/3})$. However, we can
compromise on the stretch in order to significantly decrease the label size as
we show in the following.

Subroutine create-label of $v$ computes the much smaller label
$\lambda(v):=\big{(}\text{ID}(s_{v}),d(s_{v},v)\big{)}$, where
$s_{v}:=\operatorname*{arg\,min}_{s\in S}d(s,v)$ corresponds to the identifier
and distance of the closest node in $S$.

Given some label $\lambda(u):=\big{(}\text{ID}(s_{u}),d(s_{u},v)\big{)}$ then
node $v$ outputs the following function in subroutine create-oracle-function,
which is the shorter of the $h$-hop distance to $u$ and the shortest
$v$-$u$-path that transits $s_{u}$.

(3) $o_{v}(\lambda(u))=\min\big{(}d_{h}(v,u),\,d(v,s_{u})+d(s_{u},u)\big{)}.$

We start by showing that the oracle function $o_{v}$ from above gives a decent
approximation (with proofs similar to those for approximations for the single
source shortest paths problem in [5]).

###### Lemma 2.6.

For $u,v\in V$ it is $o_{v}(u)\leq 3d(v,u)$ w.h.p. (for $o_{v}$ from Eq. (3)).

###### Proof.

If there is a shortest $v$-$u$-path with at most $h$ hops, then we actually
have $o_{v}(\lambda(u))=d_{h}(v,u)=d(v,u)$ (c.f., first argument of Equation
(3)) analogous to the proof of Theorem 2.5. Else, all shortest $v$-$u$-paths
have more than $h$ hops. Then by Lemma 2.1 w.h.p. there must be a node
$\hat{s}\in\mathcal{B}_{u,h}$ such that

$d(v,u)=d(v,\hat{s})+d(\hat{s},u).$

Let $s_{u}:=\operatorname*{arg\,min}_{s\in S}d(s,v)$ from the label
$\lambda(u)$. Then

$d(s_{u},u)\stackrel{{\scriptstyle\text{Def.\ of
}s_{u}}}{{\leq}}d(\hat{s},u)\stackrel{{\scriptstyle\text{(i)}}}{{=}}d(v,u)-d(v,\hat{s})\leq
d(v,u).$

Then, for the second argument of Equation (3) we get

c.f., Equation (3) $\displaystyle o_{v}(\lambda(u))$ $\displaystyle\leq
d(v,s_{u})+d(s_{u},u)$ triangle ineq. $\displaystyle\leq
d(v,u)+d(u,s_{u})+d(s_{u},u)$ by ineq. (ii)
$\displaystyle=d(v,u)+2d(u,s_{u})\leq 3d(v,u).$

∎

We can also express the approximation as additive error depending on largest
weight $W^{\prime}$ on some $v$-$u$-path and the hop distance $h^{\prime}$
between sampled nodes on that shortest path.

###### Lemma 2.7.

For $u,v\in V$ let $W^{\prime}$ be the largest weight on _some_ shortest
$v$-$u$-path. Then $o_{v}(\lambda(u))\leq d(v,u)+2h^{\prime}W^{\prime}$ w.h.p.
(for $o_{v}$ from Eq. (3)) where $h^{\prime}\in\smash{\widetilde{O}}(x)$
denotes the value from Lemma 2.1.

###### Proof.

Fix a shortest $v$-$u$-path $P$. Let $W^{\prime}$ be the largest weight on
$P$. By Lemma 2.1 there is a sampled node $\hat{s}\in S$ on $P$ with
$\operatorname{hop}(\hat{s},u)\leq h^{\prime}$ w.h.p.212121Note for the union
bound to work, Lemma 2.1 is phrased such that for each pair $u,v\in V$ there
is just one shortest $v$-$u$-path (out of possibly exponentially many) which
has a sampled node at last every $h^{\prime}$ hops. In fact in the proof we
can fix one specific such path for each pair ourselves and the union bound
still works. This implies $d(\hat{s},u)\leq h^{\prime}W^{\prime}$. Let
$s_{u}:=\operatorname*{arg\,min}_{s^{\prime}\in S}d(s^{\prime},v)$ (from the
label $\lambda(u)$). By definition of $s$ we have $d(s_{u},u)\leq
d(\hat{s},u)\leq h^{\prime}W^{\prime}$. Then we get

c.f., Equation (3) $\displaystyle o_{v}(\lambda(u))$ $\displaystyle\leq
d(v,s_{u})+d(s_{u},u)$ triangle ineq. $\displaystyle\leq
d(v,u)+d(u,s_{u})+d(s_{u},u)$ ∎ $\displaystyle\leq
d(v,u)+2h^{\prime}W^{\prime}.$

Similar to Equation (2), we define $\rho_{v}(\lambda(u))$ as a node $z$ that
is adjacent to $v$ such that the oracle function $o_{z}(\lambda(u))$ decreases
by at least the weight of the corresponding edge, i.e., $o_{z}(\lambda(u))\leq
o_{v}(\lambda(u))-w(v,z)$ (we will show that there is always a neighbor of $v$
that fulfills these criteria and if several do, we choose one arbitrarily).
Then subroutine create-routing-function outputs

(3) $\displaystyle\rho_{v}(\lambda(u))\in\big{\\{}z\in N(v)\mid
o_{z}(\lambda(u))\leq o_{v}(\lambda(u))-w(v,z)\big{\\}}$

###### Lemma 2.8.

For any $u,v\in V$ the routing functions in Equation (3) induce a $v$-$u$-path
$P$ with $w(P)\leq o_{v}(\lambda(u))$ w.h.p.

###### Proof.

Assume a packet is forwarded along a path $P$ containing the nodes
$v=:v_{1},\dots,v_{k}:=u$ with $o_{{i+1}}\leq o_{i}-w(v_{i},v_{i+1})$ (whereas
we abbreviate $o_{i}:=o_{v_{i}}(\lambda(u))$ and we have
$o_{k}=o_{u}(\lambda(u))=0$) then we can upper bound $w(P)$ with a telescoping
sum

$w(P)=\\!\sum_{i=1}^{k-1}\\!w(v_{i},v_{i+1})\leq\\!\sum_{i=1}^{k-1}\\!\big{(}o_{i}-o_{i+1}\big{)}=o_{1}-\underbrace{\smash{o_{k}}}_{=0}=o_{v}(\lambda(u)).$

It remains to prove the existence of $P$. For that we show that each node $v$
has a neighbor $z$ that fulfills the requirement $o_{z}(\lambda(u))\leq
o_{v}(\lambda(u))-w(v,z)$. We have to unwrap the definition of
$o_{v}(\lambda(u))$ to make this argument.

Case 1: if $o_{v}(\lambda(u))=d_{h}(v,u)$ (first argument of the $\min$
function in Equation (3)), then this means there is a $h$-hop path $Q$ from
$v$ to $u$ that fulfills $w(Q)=o_{v}(\lambda(u))$. Clearly, the next $z\in
N(v)$ on $Q$ is one hop closer to $u$ and also sees the sub-path
$Q_{z,u}\subseteq Q$ within its ball $\mathcal{B}_{z,h}$ so by Equation (3)
$z$’s distance estimate must be at least as good: $o_{z}(u)\leq
w(Q_{z,u})=o_{v}(\lambda(u))-w(v,z)$.

Case 2: if $o_{v}(\lambda(u))=d(v,s_{u})+d(s_{u},u)$, then this means our
distance estimation via $s_{u}$ is at least as good as the $h$-hop distance to
$u$ (c.f., second argument of $\min$ in Equation (3)). Let $Q$ be a path
concatenated from two shortest paths $Q_{v,s_{u}}\cup Q_{s_{u},u}$ from $v$ to
$s_{u}$ and from $s_{u}$ to $u$, respectively.

Note that $\operatorname{hop}(s_{u},u)\leq h$, as otherwise there would be a
node $s_{u}^{\prime}\in S$, $s_{u}^{\prime}\neq s_{u}$ on $Q_{s_{u},u}$ by
Lemma 2.1, which would be closer to $u$ thus contradicting the definition
$s_{u}:=\operatorname*{arg\,min}_{s\in S}d(s,u)$ in the label $\lambda(u)$.
This means that we can assume $v\neq s_{u}$ since otherwise we can apply case
1. Let $z\in N(v)$ be the next node on $Q_{v,s_{u}}$ (which contains at least
the 2 nodes $v$ and $s_{u}$, but $z=s_{u}$ is possible). Then

$\displaystyle d(v,s_{u})+d(s_{u},u)=w(v,z)+d(z,s_{u})+d(s_{u},u)$
$\displaystyle\Longrightarrow\quad$ $\displaystyle
o_{v}(\lambda(u))-w(v,z)=d(z,s_{u})+d(s_{u},u)\geq
o_{z}(\lambda(u)).\hfill\qed$

The following Theorem gives a summary of the obtained approximation algorithms
for which we utilize the previous lemmas.

###### Theorem 2.9.

Distance oracles and _stateless_ routing schemes with label-size
$\smash{O}(\log n)$ can be computed in $\mathsf{HYBRID}$ w.h.p. and

  * •

stretch 3 in $\smash{\widetilde{O}}(n^{1/3})$ rounds on weighted graphs,

  * •

stretch $1\\!+\\!\varepsilon$ for $0\\!<\\!\varepsilon\\!\leq\\!1$ in
$\smash{\widetilde{O}}\big{(}\frac{n^{1/3}}{\varepsilon}\big{)}$ rounds on
unweighted graphs.

###### Proof.

The label $\lambda(v)$ contains only the distance to the closest sampled node
in $S$ which is $\smash{O}(\log n)$ bits. For the first result on weighted
graphs we invoke Algorithm 1 with $x=n^{1/3}$ and
$h\in\smash{\widetilde{\Theta}}(x)$ as in Lemma 2.1, then the runtime follows
from Lemma 2.4 and the stretch for the resulting distance oracles follows from
Lemma 2.6. Note that by Lemma 2.8 the same stretch holds for the resulting
stateless routing scheme.

For the second result we invoke Algorithm 1 with $x=n^{1/3}$ with a wider
local exploration (by a factor $1/\varepsilon$) to distance
$h=h^{\prime}/\varepsilon$ whereas
$h^{\prime}\in\smash{\widetilde{\Theta}}(x)$ is the usual value from Lemma
2.1. Again, the runtime follows from Lemma 2.4.

The idea is that a wider local search allows us to compute shortest paths with
at most $h$ hops exactly which allows us to disregard those for proving the
stretch. By Lemma 2.7 the additive error scales only in $h^{\prime}$ which is
by a factor $1/\varepsilon$ smaller than $h$ and therefore has a relatively
small impact on the stretch of paths longer than $h$ hops.

More precisely, if $d_{h}(v,u)=d(v,u)$ then we obtain an exact distance
estimation from Equation (3). Now let $d_{h}(v,u)>d(v,u)$ meaning that all
$v$-$u$-paths with at most $h$ hops are longer than $d(v,u)$ or there exists
none such path. Then, due to the minimum edge weight of 1, we have $d(v,u)\geq
h$. Then by Lemma 2.7 we have

$\displaystyle o_{v}(\lambda(u))$ $\displaystyle\leq
d(v,u)\\!+\\!2h^{\prime}W^{\prime}=d(v,u)\\!+\\!2\varepsilon hW^{\prime}$
$\displaystyle\leq d(v,u)\\!+\\!2\varepsilon
d(v,u)=d(v,u)(1\\!+\\!2\varepsilon)$

The final result is obtained with a substitution
$\varepsilon^{\prime}:=2\varepsilon$. ∎

##  3\. Node Communication Problem

In the remaining sections of this paper we will completely focus on
computational lower bounds. This section is dedicated to creating an
“information bottleneck” in the $\mathsf{HYBRID}$ model between two (distant)
parts of the local communication graph. We do this for the more general
$\mathsf{HYBRID}(\infty,\gamma)$ model, where we have a global communication
bandwidth of $\gamma$ bits per node per round. Besides the advantage of having
a more general lower bound, this avoids logarithmic terms and
$\smash{O}$-notation as long as possible (recall that
$\mathsf{HYBRID}=\mathsf{HYBRID}\big{(}\infty,\smash{O}(\log^{2}n)\big{)}$).

We start with some intuition. Let $G=(V,E)$ be a graph. Assume that
information, formalized as the state of some random variable $X$, is
collectively known by nodes $A\subset V$ and must be learned by some set
$B\subset V$ disjoint from $A$. This information either has to travel the hop
distance $h:=hop(A,B)$ from $A$ to $B$ along the unrestricted local network,
which takes $h$ rounds. If we want to be faster than that, each bit traveling
from $A$ to $B$ has to use a global edge eventually. Thus the number of rounds
is at least the “total amount” of information (given by the entropy
$H(X)$222222The Shannon entropy of random variable $X\\!:\\!\Omega\\!\to\\!S$
is defined as $H(X):=-\\!\sum_{x\in
S}\mathbb{P}(X\\!=\\!x)\log\big{(}\mathbb{P}(X\\!=\\!x)\big{)}$ [25].),
divided by the overall global communication capacity of at most $n\cdot\gamma$
bits in the $\mathsf{HYBRID}(\infty,\gamma)$ model.

To prove this formally and in a more general form, we first introduce some
definitions. We say that the nodes from some set $A\subseteq V$ collectively
know the state of a random variable $X$, if its state can be derived from the
information that the nodes $A$ have. Or, in terms of information theory, given
the state or input $S_{A}$ of all nodes $A$ (interpreted as a random
variable), then the conditional entropy $H(X|S_{A})$ also known as the amount
of new information of $X$ provided that $S_{A}$ is already known, is zero.
Similarly, we say that the state of $X$ is unknown to $B\subseteq V$, if the
initial information of the nodes $B$ does not induce any knowledge on the
outcome of $X$. Or formally, that for the state $S_{B}$ of the nodes $B$ we
have that $H(X|S_{B})=H(X)$, meaning that all information in $X$ is new even
if $S_{B}$ is known. Another way of expressing this is that $S_{B}$ and $X$
are stochastically independent.

###### Definition 3.1 (Node Communication Problem).

Let $G=(V,E)$ be some graph. Let $A,B\subset V$ be disjoint sets of nodes and
$h:=hop(A,B)$. Furthermore, let $X$ be a random variable whose state is
collectively known by the nodes $A$ but unknown to any set of nodes disjoint
from $A$. An algorithm $\mathcal{A}$ solves the _node communication problem_
if the nodes in $B$ collectively know the state of $X$ after $\mathcal{A}$
terminates. We say $\mathcal{A}$ has success probability $p$ if $\mathcal{A}$
solves the problem with probability at least $p$ for _any_ state $X$ can
take.232323In line with our Definition 1.6 of success probability for graph
algorithms.

The goal of Lemma 3.3 is to reduce a more basic communication problem, for
which we can provide lower bounds using basic information theory (c.f.,
Appendix B) to the node communication problem. Analogously to node sets, we
define that Alice knows some random variable $X$, which is unknown to Bob as
follows. Given that $S_{\text{Alice}}$ and $S_{\text{Bob}}$ are their
respective inputs then we have $H(X|S_{\text{Alice}})=0$ and
$H(X|S_{\text{Bob}})=H(X)$.

###### Definition 3.2 (Two Party Communication Problem).

Given two computationally unbounded parties, Alice and Bob, where initially
Alice knows the state of some random variable $X$ which is unknown to Bob. A
communication protocol $\mathcal{P}$ is said to solve the problem if after the
execution of $\mathcal{P}$ Bob can derive the state of $X$ from the transcript
of all exchanged messages. Performance is measured in the length of the
transcript in bits. We say $\mathcal{P}$ has success probability $p$ if
$\mathcal{P}$ solves the problem with probability at least $p$ for _any_ state
$X$ can take.

The reduction from the 2-party communication problem to the node communication
problem uses a simulation argument similar to the one in [18]. We show that
Alice and Bob can together simulate a $\mathsf{HYBRID}(\infty,\gamma)$ model
algorithm for the node communication problem and use it solve the 2-party
communication problem.

###### Lemma 3.3.

Any algorithm $\mathcal{A}$ that solves the _node communication problem_ (Def.
3.1) in the $\mathsf{HYBRID}(\infty,\gamma)$ model on some local graph
$G=(V,E)$ with $n=|V|$ and $A,B\subset V$ in $T<h=hop(A,B)$ rounds with
success probability $p$ can be used to obtain a protocol $\mathcal{P}$ that
solves the two party communication problem (Def. 3.2) with the same success
probability $p$ and transcript length at most $T\cdot n\cdot\gamma$.

###### Proof.

We will derive a protocol $\mathcal{P}$ that uses (i.e., simulates) algorithm
$\mathcal{A}$ in order to solve the two-party communication problem. First we
make a few assumptions about the initial knowledge of both parties in
particular about the graph $G$ from the node communication problem, you can
think of this information as hard coded into the instructions of
$\mathcal{P}$. The important observation is that none of these assumptions
will give Bob any knowledge about $X$.

Specifically, we assume that Alice is given complete knowledge of the topology
$G$ and inputs of all nodes in $G$ (in particular the state of $X$ and the
source codes of all nodes specified by $\mathcal{A}$). Bob is given the same
for the subgraph induced by $V\setminus A$, which means that the state of $X$
remains unknown to Bob (c.f., Def. 3.1). To accommodate randomization of
$\mathcal{A}$, both are given the same copy of a string of random bits
(determined randomly and independently from $X$) that is sufficiently long to
cover all “coin flips” used by any node in the execution of $\mathcal{A}$.

Alice and Bob simulate the following nodes during the simulated execution of
algorithm $\mathcal{A}$. For $i\in[h\\!-\\!1]$ let $V_{i}:=\\{v\in
V\mid\operatorname{hop}(v,A)\leq i\\}$ be the set of nodes at hop distance at
most $i$ from $A$. Note that $A\subseteq V_{i}$ for all $i$. In round 0 of
algorithm $\mathcal{A}$, Alice simulates all nodes in $A$ and Bob simulates
all nodes in $V\setminus A$. However, in subsequent rounds $i>0$, Alice
simulates the larger set $A\cup V_{i}$ and Bob simulates the smaller set
$B\cup V\setminus V_{i}$.

Figuratively speaking, in round $i$ Bob will relinquish control of all nodes
that are at hop distance $i$ from set $A$, to Alice. This means, in each
round, every node is simulated either by Alice or by Bob. We show that each
party can simulate their nodes correctly with an induction on $i$. Initially
($i=0$), this is true as each party gets the necessary inputs of the nodes
they simulate. Say we are at the beginning of round $i>0$ and the simulation
was correct so far. It suffices to show that both parties obtain all messages
that are sent (in the $\mathsf{HYBRID}(\infty,\gamma)$ model) to the nodes
they currently simulate.

The communication taking place during execution of $\mathcal{A}$ in the
$\mathsf{HYBRID}(\infty,\gamma)$ model is simulated as follows. If two nodes
that are currently simulated by the _same_ party, say Alice, want to
communicate, then this can be taken care as part of the internal simulation by
Alice. If a node that is currently simulated (w.l.o.g.) by Bob wants to send a
message over the _global_ network to some node that Alice simulates, then Bob
sends that message directly to Alice as part of $\mathcal{P}$, and that
message becomes part of the transcript.

Now consider the case where a local message is exchanged between some node $u$
simulated by Alice and some node $v$ simulated by Bob. Then in the subsequent
round Alice will always take control of $v$, as part of our simulation regime.
Thus Alice can continue simulating $v$ correctly as she has all information to
simulate all nodes all the time anyway (Alice is initially given all inputs of
all nodes). Therefore it is not required to exchange any local messages across
parties for the correct simulation.

After $T$ simulated rounds, Bob, who simulates the set $B$ until the very end
(as $T<h$), can derive the state of $X$ from the local information of $B$ with
success probability at least $p$ (same as algorithm $\mathcal{A}$). Hence,
using the global messages that were exchanged between Alice and Bob during the
simulation of algorithm $\mathcal{A}$ we obtain a protocol $\mathcal{P}$ that
solves the two party communication problem with probability $p$. Since total
global communication is restricted by $n\cdot\gamma$ bits per round in the
$\mathsf{HYBRID}(\infty,\gamma)$ model, Alice sends Bob at most $T\cdot
n\cdot\gamma$ bits during the whole simulation. ∎

Next we plug in the lower bound for the 2-party communication problem (c.f.
Lemma B.3 in Appendix B) to derive a lower bound for the node communication
problem. Note that this theorem only depends on the hop distance $h$ between
$A,B$ and the entropy of $X$ and is otherwise agnostic to the local graph.
Note that a lower bound that holds in expectation is also a worst case lower
bound.242424A worst case lower bound means there exists one outcome of $X$
where the algorithm takes at least that many rounds. A lower bound that holds
in expectation clearly implies the same in the worst case.

###### Theorem 3.4.

Any algorithm that solves the node communication problem (Def. 3.1) on some
$n$-node graph in the $\mathsf{HYBRID}(\infty,\gamma)$ model with success
probability at least $p$, takes at least
$\min\\!\big{(}\frac{pH(X)-1}{n\cdot\gamma},h\big{)}$ rounds in expectation,
where $H(X)$ denotes the entropy of $X$.

###### Proof.

We have to show that a randomized, $\mathsf{HYBRID}(\infty,\gamma)$ algorithm
$\mathcal{A}$ that solves the node communication problem in less than $h$
rounds with success probability $p$ takes at least
$\frac{pH(X)-1}{n\cdot\gamma}$ rounds. Presume, for a contradiction, that
$\mathcal{A}$ has an expected running time $T<h$ and
$T<\frac{pH(X)-1}{n\cdot\gamma}$. This implies $T\cdot n\cdot\gamma<p\cdot
H(X)-1$.

Invoking Lemma 3.3 gives us a protocol $\mathcal{P}$ with the same success
probability $p$ and with a transcript of length at most $T\cdot n\cdot\gamma$.
With the inequality above, this means in the protocol $\mathcal{P}$, Alice
sends less than $p\cdot H(X)-1$ bits to Bob in expectation. This contradicts
the fact that $p\cdot H(X)-1$ is a lower bound for this due to Appendix B
Lemma B.3.∎

We have to accommodate the fact that in the routing problem or distance oracle
problem, the nodes have to give a distance estimation or next routing neighbor
only when provided with the label of the target node. Therefore we have to
slightly amend Theorem 3.4, which will later allow us to argue that even if we
assume that nodes have advance knowledge of a selection of sufficiently small
labels, the lower bound will not change asymptotically.

###### Corollary 3.5.

If $A$ is allowed to communicate $y$ bits to $B$ for free, then any algorithm
that solves the node communication problem on some $n$-node graph (Def. 3.1)
in the $\mathsf{HYBRID}(\infty,\gamma)$ model with success probability at
least $p$, takes at least
$\min\\!\big{(}\frac{pH(X)-1-y}{n\cdot\gamma},h\big{)}$ rounds in expectation
(i.e., also in the worst case).

###### Proof.

As above, the node communication problem reduces to the communication problem
between Alice and Bob, where Alice is now allowed to send $y$ bits to Bob in
advance. Note that this still requires Alice to send $p\cdot H(X)-1-y$
remaining bits in expectation, as per Lemma B.3. The same contradiction as in
Theorem 3.4 can be derived as follows. Fewer rounds than stated in this lemma
would imply that the transcript of global messages from Alice to Bob, would be
shorter than $p\cdot H(X)-1-y$ bits (essentially by substituting $p\cdot
H(X)-1$ for $p\cdot H(X)-1-y$ in the previous proof). Thus the transcript
would be less than $p\cdot H(X)-1$ bits even when we add the $y$ “free” bits
to the transcript. ∎

##  4\. Lower Bounds For Unweighted Graphs

In this and the following section we aim to reduce from the node communication
problem in the $\mathsf{HYBRID}(\infty,\gamma)$ model given in Definition 3.1,
to the problem of computing routing tables or distance oracles, which works as
follows.

We define a graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ such that, first, the
solution of the routing or distance oracle problems informs a subset $B\subset
V_{\Gamma}$ about the exact state of some random variable $X$ that is encoded
by the subgraph induced by $A\subset V_{\Gamma}$. Second, $X$ has a large
entropy (we aim for super-linear in $n$). And third, the distance $hop(A,B)$
between both sets is sufficiently large.

###### Definition 4.1.

Let $X=(x_{ij})_{i,j\in[k]}\in\\{0,1\\}^{k^{2}}$ be a bit sequence of length
$k^{2}$. Let $\Gamma=(V_{\Gamma},E_{\Gamma})$ (shown in Figure 1) be an
unweighted graph with source nodes $s_{1},\dots,s_{k}\in V_{\Gamma}$, transit
nodes $u_{1},\dots,u_{k}\in V_{\Gamma}$ and target nodes $t_{1},\dots,t_{k}\in
V_{\Gamma}$. Each source $s_{i}$ has a path of length $h$ hops to the transit
nodes $u_{i}$. We have an edge between $u_{i}$ and $t_{j}$ if and only if
$x_{ij}=1$. Additionally, there are two nodes $v,v^{\prime}\in V_{\Gamma}$
connected by a path of $h$ hops. The nodes $v$ and $v^{\prime}$ have an edge
to each source $s_{i}$ or target $t_{i}$, respectively (Figure 1).

This construction has the following properties.

  1. (1)

The distance from source $s_{i}$ to $t_{j}$ is larger for $x_{ij}=0$ than for
$x_{ij}=1$ (as shown by the subsequent Lemma 4.2).

  2. (2)

For all $i,j\in[k]$, independently set $x_{ij}=1$ with probability
$\frac{1}{2}$, else $x_{ij}=0$. This maximizes
$H(X)=-k^{2}\cdot\frac{\log(1/2)}{2}=\frac{k^{2}}{2}$.

  3. (3)

Let $A\\!=\\!\\{u_{1},...\,,u_{k},t_{1},...\,,t_{k}\\}$,
$B\\!=\\!\\{s_{1},...\,,s_{k}\\}$, i.e., $hop(A,B)\\!=\\!h$.

Figure 1.  Graph $\Gamma=(V_{\Gamma},E_{\Gamma})$. Bit string $X=(x_{ij})$
determines red edges. E.g., $\\{u_{1},t_{2}\\}\\!\notin\\!E_{\Gamma}$ and
$\\{u_{1},t_{3}\\}\\!\in\\!E_{\Gamma}$ means $x_{12}=0$ and $x_{13}=1$,
respectively.

Property (1) is shown by the following lemma.

###### Lemma 4.2.

If $x_{ij}\\!=\\!1$ then $d(s_{i},t_{j})=h\\!+\\!1$ and the shortest
$s_{i}$-$t_{j}$-path contains $v$, else $d(s_{i},t_{j})=h\\!+\\!2$ and it does
not contain $v$.252525In the following, distances without subscript will refer
to distances in $\Gamma$, i.e., $d(u,v):=d_{\Gamma}(u,v)$.

###### Proof.

Any path from $s_{i}$ to $t_{j}$ has to cross the vertex cut
$U:=\\{u_{1},\dots,u_{k},v^{\prime}\\}$ (c.f., Figure 1). Such a path has to
include a path of length $h$ to reach a node of $U$, as well as an additional
edge connecting $U$ to $t_{j}$ and therefore $d(s_{i},t_{j})\geq h+1$.
However, we also have $d(s_{i},t_{j})\leq h+2$, due to the path along the
nodes $s_{i},v,\ldots,v^{\prime},t_{j}$ (c.f., Figure 1) that has length
$h+2$.

If $x_{ij}=1$, i.e., $\\{u_{i},t_{j}\\}\in E$, then the path along the nodes
$s_{i},\ldots,u_{i},t_{j}$ has length $h+1$. Note that all nodes in
$U\setminus\\{u_{i},v^{\prime}\\}$ are at distance at least $h+2$ from $s_{i}$
(c.f., Figure 1), so every path via one of the nodes
$U\setminus\\{u_{i},v^{\prime}\\}$ has distance at least $h+3$. In the case
$x_{ij}=0$, i.e., $\\{u_{i},t_{j}\\}\notin E_{\Gamma}$, this is also true for
the path via $u_{i}$ and the only path with distance $h+2$ is the one via
$v^{\prime}$. ∎

The idea to prove the next theorem is that if the nodes in $B$ learn the
distance to the nodes in $t_{1},\dots,t_{k}$, then their combined knowledge
can be used to infer the state of the random string $X$ that is collectively
known by the nodes in $A$.

###### Theorem 4.3.

Even on _unweighted graphs_ , any randomized algorithm that computes exact
(stateless or stateful) routing schemes or distance oracles in the
$\mathsf{HYBRID}(\infty,\gamma)$ model with constant success probability takes
$\Omega(n^{1/3}/\gamma^{1/3})$ rounds. This holds for labels of size up to
$c\cdot n^{2/3}\cdot\gamma^{1/3}$ (for a fixed constant $c>0$).

###### Proof.

Consider an algorithm $\mathcal{A}$ that computes exact routing schemes or
distance oracles for $\Gamma$ with constant probability at least $p$. Assuming
that the nodes in $B$ are given the distance labels for the nodes
$\\{t_{1},\dots,t_{k}\\}$ in advance then after algorithm $\mathcal{A}$ has
terminated, every node $s_{i}\in B$ either knows its distance $d(s_{i},t_{j})$
for every $t_{j}$ (distance oracles) or it knows if the next node on the
corresponding shortest path is $v$ or not (routing schemes).

Then, by Lemma 4.2, every node $s_{i}$ can infer for every $t_{j}$ if
$x_{ij}=0$ or $x_{ij}=1$, which means that the nodes in $B$ collectively know
the state of $X$. Note that this corresponds to the node communication problem
of Definition 3.1, with the caveat that we assumed nodes in $B$ have advance
knowledge of the labels $\lambda(t_{1}),\dots,\lambda(t_{k})$. The combination
of these labels can contain information at most
$y:=\sum_{i=1}^{k}|\lambda(t_{i})|$ bits, which we allow $A$ to communicate to
$B$ “for free”. By Corollary 3.5, algorithm $\mathcal{A}$ takes at least
$\min\\!\big{(}\frac{pH(X)-1-y}{n\cdot\gamma},h\big{)}$ rounds.

The total number of nodes of $\Gamma$ is $n\in\Theta(h\cdot k)$, which leaves
one degree of freedom for $k$ and $h$. We choose
$k\in\Theta(n^{2/3}\gamma^{1/3})$ and $h\in\Theta(n^{1/3}/\gamma^{1/3})$. This
implies $H(X)\in\Theta(n^{4/3}\gamma^{2/3})$ by property (2) (see further
above). For labels of size $c\cdot n^{2/3}\gamma^{1/3}$, we have
$y=c\cdot\Theta(n^{4/3}\gamma^{2/3})$. We simply choose the constant $c>0$
small enough so that $cn^{4/3}\gamma^{2/3}\leq\frac{pH(X)-1}{2}$ (i.e., $y$
will not change the lower bound asymptotically). Plugging all of the above
into the lower bound of
$\min\\!\big{(}\frac{pH(X)-1-y}{n\cdot\gamma},h\big{)}$ rounds, yields the
desired bound of $\Omega(n^{1/3}/\gamma^{1/3})$ rounds. ∎

##  5\. Lower Bounds for Approximations

Our next construction relies on the existence of families of graphs that have
high girth and maintain relatively high density. We modify the basic
construction above, essentially by replacing the upper part of $\Gamma$ with a
random selection of edges from a graph of that family (and also making
$\Gamma$ weighted). Besides high density we require the following.

###### Definition 5.1.

$\mathcal{G}_{k,\ell}$ is a graph family, s.t. for all
$G\\!=\\!(A,E)\\!\in\\!\mathcal{G}_{k,\ell}$

  1. (i)

$|A|=2k$

  2. (ii)

$G$ has (even) girth at least $\ell$

  3. (iii)

$G$ is balanced and bipartite

###  5.1. Weighted Construction

Removing an edge from $G\in\mathcal{G}_{k,\ell}$ incurs a large detour of at
least $\ell\\!-\\!1$ hops between the endpoints of that edge, since otherwise
there would be a cycle shorter than $\ell$ in $G$. This observation is often
used to prove certain bounds for low stretch subgraphs262626One prominent
example is the lower bound on the size of low stretch spanners. and can be
exploited to introduce a stretch into our lower bound construction. We
construct this formally as follows (however, first consulting Figure 2 will
presumably be more helpful to the reader).

Figure 2.  Graph $\Gamma$ constructed around $G=(A,E)\in\mathcal{G}_{k,\ell}$
with $m:=|E|$ edges (in red) and from the bit string $X=(x_{e})_{e\in
E}\in\\{0,1\\}^{m}$. An edge $e\in E$ is part of $\Gamma$ iff $x_{e}=1$. For
instance $\\{u_{2},t_{3}\\}\in E$ but $x_{\\{u_{2},t_{3}\\}}=0$, so
$\\{u_{2},t_{3}\\}\notin E_{\Gamma}$. Edge weights
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{0}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}w_{1}},{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}w_{2}}$
are indicated with colored edges, all others have weight 1.

###### Definition 5.2.

Let $G=(A,E)\in\mathcal{G}_{k,\ell}$ with $m:=|E|$ edges and let
$\\{u_{1},\dots,u_{k}\\}\cup\\{t_{1},\dots,t_{k}\\}=A$ be the bipartition of
$G$. Graph $\Gamma=(V_{\Gamma},E_{\Gamma})$ (shown in Figure 2) has a similar
structure as the unweighted construction (Def. 4.1), where the main difference
is the way how the nodes $\\{u_{1},\dots,u_{k}\\}\cup\\{t_{1},\dots,t_{k}\\}$
are connected by edges in $\Gamma$.

Let $X=(x_{e})_{e\in E}\in\\{0,1\\}^{m}$ be a bit string of length $m=|E|$,
i.e., each bit $x_{e}$ corresponds to an edge $e$ of $G$. For each
$u_{i},t_{j}$ we have $\\{u_{i},t_{j}\\}\in E_{\Gamma}$, if and only if
$\\{u_{i},t_{j}\\}\in E$ and $x_{\\{u_{i},t_{j}\\}}=1$. In a slight change
from the previous construction, we make the path from $v$ to $v^{\prime}$ of
hop length $h\\!-\\!1$. The weights of $\Gamma$ are assigned as follows. Edges
between the node $v^{\prime}$ and some $t_{j}$ have weight $w_{0}$. Edges
between nodes $u_{i},t_{j}$ have weight $w_{1}$. Edges incident to some
$s_{i}$ have weight $w_{2}$.

We have the following properties.

  1. (1)

Let $e\\!=\\!\\{u_{i},t_{j}\\}\\!\in\\!E$. $w_{0},w_{1},w_{1}$ can be chosen
s.t. $d(s_{i},t_{j})$ is much longer for $x_{e}=0$ than for $x_{e}=1$ (c.f.,
Lemma 5.3).

  2. (2)

For each edge $e\in E$ of $G$, set $x_{e}=1$ i.i.d. with probability
$\frac{1}{2}$, else $x_{e}=0$. This maximizes the entropy $H(X)=\frac{m}{2}$.

  3. (3)

For nodes $A$ of $G$ and $B:=\\{s_{1},\dots,s_{k}\\}$ we have
$\operatorname{hop}(A,B)=h$.

We analyze distances $d(s_{i},t_{j})$ between nodes $s_{i},t_{j}$ with
$e=\\{u_{i},t_{j}\\}\in E$ for the two cases that $e$ is part of $\Gamma$
($x_{e}=1$), or not ($x_{e}=0$). Conceptually, we choose weights $w_{1}\ll
w_{0}$, such that we can observe a large difference in $d(s_{i},t_{j})$
depending on $x_{e}$.

###### Lemma 5.3.

Consider $\Gamma$ (Def. 5.2), constructed from
$G=(A,E)\in\mathcal{G}_{k,\ell}$ and $X$. Let $w_{1}<w_{0}<(\ell-1)w_{1}$. Let
$e=\\{u_{i},t_{j}\\}\in E$. Then we have:

  1. (i)

The shortest $s_{i}$-$t_{j}$-path contains $v$ if and only if $x_{e}=0$.

  2. (ii)

If $x_{e}=1$ then $d(s_{i},t_{j})=w_{2}+w_{1}+h-1$.
If $x_{e}=0$, then $d(s_{i},t_{j})=w_{2}+w_{0}+h-1$.

###### Proof.

Let $U:=\\{u_{1},\dots,u_{k},v\\}$ be the vertex cut that separates any
$s_{i}$ from any $t_{j}$. The shortest simple $s_{i}$-$t_{j}$-path that
crosses $U$ via $v$ has length $w_{2}+w_{0}+h-1$ independently from $x_{e}$
(simple implies that a path can not “turn around” and go via $u_{i}$).

Consider the shortest $s_{i}$-$t_{j}$-path that does not contain $v$. In the
case $x_{e}=1$, i.e., $e=\\{u_{i},t_{j}\\}$ exists in $\Gamma$, this
$s_{i}$-$t_{j}$-path is forced to cross $U$ via $u_{i}$ and then goes directly
to $t_{j}$ via $e$, and thus has length $w_{2}+w_{1}+h-1$.

Let us analyze the length of the $s_{i}$-$t_{j}$-path that does not contain
$v$ for the case $x_{e}=0$ (i.e., $e\notin E_{\Gamma}$). Let $G^{\prime}$ be
the subgraph that corresponds to $G$ after removing each edge $e^{\prime}\in
E$ with $x_{e^{\prime}}=0$. Then that $s_{i}$-$t_{j}$-path has to traverse
$G^{\prime}$ to reach $t_{j}$. The sub-path from $u_{i}$ to $t_{j}$ in
$G^{\prime}$ has to use at least $(\ell\\!-\\!1)$ edges, because otherwise
$e=\\{u_{i},t_{j}\\}$ would close a loop of less than $\ell$ edges in
$G^{\prime}$ (and thus also in $G$), contradicting the premise that $G$ has
girth $\ell$. Thus, for $e\notin E_{\Gamma}$ any $s_{i}$-$t_{j}$-path that
does not contain $v$ has length at least $w_{2}+(\ell\\!-\\!1)w_{1}+h-1$.

We sum up the cases. If $x_{e}=1$, then the $s_{i}$-$t_{j}$-path not
containing $v$ of length $w_{2}+w_{1}+h-1$ is shorter than the one via $v$ of
length $w_{2}+w_{0}+h-1$, since $w_{1}<w_{0}$. If $x_{e}=0$, then the
$s_{i}$-$t_{j}$-path via $v$ of length $w_{2}+w_{0}+h-1$ is shorter than the
one not containing $v$ of length at least $w_{2}+(\ell-1)w_{1}+h-1$ due to
$w_{0}<(\ell\\!-\\!1)w_{1}$. ∎

For the reduction from the node communication problem to our concrete routing
and distance oracle problems, we start with a technical lemma that analyzes
the running time of any algorithm $\mathcal{A}$ that solves the node
communication problem in $\Gamma$ for the dedicated node sets $A,B$ and the
random variable $X$ from which $\Gamma$ is constructed.

In particular, we express the lower bound from Theorem 3.4 as function of
$n:=|V_{\Gamma}|$, the density of $G\in\mathcal{G}_{k,\ell}$ given by a
parameter $\delta$ and the global communication capacity $\gamma$. The lemma
is the result of balancing a trade off between the distance
$h=\operatorname{hop}(A,B)$ and the number of nodes $\Theta(k)$ of $G$ (which
governs the entropy $H(X)=\Theta(k^{1+\delta})$ when the density of $G$ is
fixed).272727Naturally, the number of edges $\Theta\big{(}k^{1+\delta}\big{)}$
of $G\in\mathcal{G}_{k,\ell}$ is also bounded through
$\delta<\frac{\ell-1}{2}$, c.f., Lemma C.2 in Appendix C.

###### Lemma 5.4.

Consider $\Gamma$ constructed from random variable $X$ and
$G=(A,E)\in\mathcal{G}_{k,\ell}$ (Def. 5.2) with
$|E|=\Theta\big{(}k^{1+\delta}\big{)}$ edges (for $\delta>0$ and $k$ of our
choosing). Let $\mathcal{A}$ be an algorithm that solves the node
communication problem on $\Gamma$ with $X$, node sets $A,B\subset V_{\Gamma}$
and $h=hop(A,B)$ in the $\mathsf{HYBRID}(\infty,\gamma)$ model (all parameters
as in Def. 5.2). We can choose $k=\Theta\big{(}\frac{n}{h}\big{)}$ such that
$\mathcal{A}$ takes
$\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$
rounds. There exists a constant $c>0$ such that this holds even when we allow
exchanging $c\cdot k^{1+\delta}$ bits from $A$ to $B$ for free.

###### Proof.

As $\mathcal{A}$ solves the node communication problem (Def. 3.1) it takes at
least $\min\\!\big{(}\frac{pH(X)-1-y}{n\cdot\gamma},h\big{)}$ rounds by
Corollary 3.5, where $H(X)\in\Theta(k^{1+\delta})$ (see property (2), further
above), $p$ is the constant success probability and $y$ describes the “free”
communication.

The arguments of $\min\\!\big{(}\frac{pH(X)-1-y}{n\cdot\gamma},h\big{)}$
behave inversely, since increasing the distance $h=hop(A,B)$ leaves only
$k\in\Theta\big{(}\frac{n}{h}\big{)}$ nodes for the graph $G$, which decreases
$H(X)\in\Theta(k^{1+\delta})$. So in order to maximize the number of rounds
given by the min function, we solve the equation
$\frac{pH(X)-1-y}{n\cdot\gamma}=h$ subject to $k\cdot h=\Theta(n)$. Slashing
constants and neglecting $y$ for now, this simplifies as follows

$\Theta\big{(}\tfrac{k^{1+\delta}}{n\cdot\gamma}\big{)}=\Theta(h),\quad\text{subject
to}\quad k\cdot h=\Theta(n).$

The solution is
$k=\Theta\big{(}n^{\frac{2}{2+\delta}}\cdot\gamma^{\frac{1}{2+\delta}}\big{)}$
and
$h=\Theta\big{(}n^{\frac{\delta}{2+\delta}}/\gamma^{\frac{1}{2+\delta}}\big{)}$
(which the willing reader may verify by inserting), resulting in a lower bound
of
$\Omega(n^{\frac{\delta}{2+\delta}}/\gamma^{\frac{1}{2+\delta}})=\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$
rounds.

When we factor the free communication of $y=c\cdot k^{1+\delta}$ bits back
into the equation $\frac{pH(X)-1-y}{n\cdot\gamma}=h$, then there are no
asymptotic changes to the outcome of our calculations as long as we choose the
constant $c$ such that $c\cdot k^{1+\delta}\leq\frac{pH(X)-1}{2}$ (for all $n$
bigger than some constant $n_{0}$). ∎

###  5.2. Distance Oracles

The first lower bound with stretch is for the distance oracle problem. The
idea is as follows. In case there is a direct edge $e=\\{u_{i},t_{j}\\}$
(i.e., $x_{e}=1$), the distance from $s_{i}$ to $t_{j}$ is almost
$\ell\\!-\\!1$ times shorter, than if that is not the case. Hence, by learning
an approximation of $d(s_{i},t_{j})$ with a stretch slightly lower than
$\ell\\!-\\!1$, the node $s_{i}$ can conclude if $e$ exists or not, i.e., if
$x_{e}=1$ or $x_{e}=0$. Hence the nodes $B=\\{s_{1},\dots,s_{k}\\}$
collectively learn the random variable $X$ and thus solve the node
communication problem.282828Note that for the distance oracles lower bound,
the path from $v$ to $v^{\prime}$ could be removed from $\Gamma$, since
$s_{i}$ learns $x_{e}=x_{\\{s_{i},t_{j}\\}}$ from the distance estimate to
$t_{j}$ and not from the next routing node. Since it does not hurt either, we
keep $\Gamma$ uniform for all our lower bounds.

This lemma is kept general such that we can later plug in any graph with a
given density parameter $\delta$ and girth $\ell$. Note that the girth $\ell$
fundamentally limits the density parameter $\delta$; the correspondence
between the two is roughly $\delta\in\smash{O}\big{(}\frac{1}{\ell}\big{)}$ as
shown in Appendix C. For a more intuitive understanding we suggest plugging in
the complete bipartite graph $G_{k,k}$ which has girth $\ell=4$ and
$\Theta(k^{2})$ edges (i.e., density parameter $\delta=1$).

###### Lemma 5.5.

Consider $\Gamma$ constructed from $G=(A,E)\in\mathcal{G}_{k,\ell}$ with
$|E|=\Theta\big{(}k^{1+\delta}\big{)}$ edges for some $\delta>0$. Any
algorithm that solves the _distance oracle problem_ on $\Gamma$ with stretch
$\alpha_{\ell}=\ell\\!-\\!1\\!-\\!\varepsilon$ (for any const.
$\varepsilon>0$) and constant success probability in the
$\mathsf{HYBRID}(\infty,\gamma)$ model takes
$\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$
rounds, for labels up to size $c\cdot
n^{\frac{2\delta}{2+\delta}}\cdot\gamma^{\frac{\delta}{2+\delta}}$ (for a
fixed const. $c>0$).

###### Proof of Lemma 5.5.

Set $w_{2}=1$ (this weight is only needed later for stateful routing scheme
lower bounds). To make the idea described above work, we have to make the
unweighted edges of $\Gamma$ (the $h$-hop $s_{i}$-$u_{i}$-paths) insignificant
for the approximation ratio by scaling the weights $w_{1},w_{0}$ by a large
factor $t$. For that purpose we introduce the parameter $t>0$, which is
specified later. We choose $w_{1}=t$ and
$w_{0}=(\ell\\!-\\!1\\!-\\!\frac{\varepsilon}{2})\cdot t$. In particular, this
means $w_{1}<w_{0}<(\ell-1)w_{1}$ (the precondition of Lemma 5.3).

Let $e=\\{u_{i},t_{j}\\}\in E$. Let $d_{1}=d(s_{i},t_{j})$ for the case
$x_{e}=1$ and $d_{0}=d(s_{i},t_{j})$ for the case $x_{e}=0$. By Lemma 5.3, we
know that $d_{1}=t\\!+\\!h$ and
$d_{0}=(\ell\\!-\\!1\\!-\\!\frac{\varepsilon}{2})\cdot t+h$. Let $\mathcal{A}$
be an approximation algorithm for the distance oracle problem with stretch
$\alpha_{\ell}=\ell\\!-\\!1\\!-\\!\varepsilon$.

For the cases $x_{e}=1$ and $x_{e}=0$, respectively, let $\tilde{d}_{1}$ and
$\tilde{d}_{0}$ be distance approximations of $d(s_{i},t_{j})$ with stretch
$\alpha_{\ell}$ that $s_{i}$ determines with its local table and the label of
$t_{j}$ (which we computed with $\mathcal{A}$). Note that our claims about
$\tilde{d}_{0},\tilde{d}_{1}$ will only depend on $x_{e}$ and are independent
from $x_{e^{\prime}}$ of other edges $e^{\prime}\in E\setminus\\{e\\}$ (even
though the exact value of $\tilde{d}_{0},\tilde{d}_{1}$ might depend on the
$x_{e^{\prime}}$).

The goal is to show $\tilde{d}_{1}<d\leq\tilde{d}_{0}$ for some constant
$d>0$, which enables $s_{i}$ to distinguish $x_{e}=1$ from $x_{e}=0$ from its
approximation of $d(s_{i},t_{j})$. We know that
$\tilde{d}_{1}\leq\alpha_{\ell}\cdot
d_{1}=(\ell\\!-\\!1\\!-\\!\varepsilon)(t\\!+\\!h)$. We also have
$\tilde{d}_{0}\geq d_{0}$ since our approximations are supposed to be one-
sided. Then

$\displaystyle\tilde{d}_{1}$
$\displaystyle\leq(\ell\\!-\\!1\\!-\\!\varepsilon)(t\\!+\\!h)$ expand
$\displaystyle=(\ell\\!-\\!1\\!-\\!\tfrac{\varepsilon}{2})\cdot
t+h+(\ell\\!-\\!2\\!-\\!\varepsilon)\cdot h-\tfrac{\varepsilon}{2}\cdot t$ for
large enough $t$
$\displaystyle<(\ell\\!-\\!1\\!-\\!\tfrac{\varepsilon}{2})\cdot t+h$
$\displaystyle=d_{0}\leq\tilde{d}_{0}.$

The strict inequality is obtained by choosing
$t>\frac{2(\ell-2-\varepsilon)}{\varepsilon}\cdot h\in\Theta(\frac{\ell
h}{\varepsilon})$. Note that edge weights remain polynomial in $n$ with this
choice of $t$ since $\ell,h\in O(n)$ and $\varepsilon$ is constant. So we get
$\tilde{d}_{1}<d_{0}\leq\tilde{d}_{0}$, which implies the following. Let
$\tilde{d}(s_{i},t_{j})$ be the distance estimate that $s_{i}$ actually
outputs. Then it is $x_{e}=0$ if $\tilde{d}(s_{i},t_{j})<d_{0}$, else it is
$x_{e}=1$. Hence the nodes $B:=\\{s_{1},\dots,s_{k}\\}$ collectively learn $X$
and thus solve the node communication problem, which takes
$\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$ rounds
by Lemma 5.4.

Two things remain to be mentioned. First, we can assume that each $s_{i}$ also
has advance knowledge of $d_{0}$, as this does not carry any information about
$X$ to the nodes $B=\\{s_{1},\dots,s_{k}\\}$ and therefore does not make the
node communication problem easier.

Second, the nodes $s_{i}$ can only produce the distance estimations
$\tilde{d}(s_{i},t_{j})$ when they are also provided with the labels
$\lambda(t_{1}),\dots,\lambda(t_{k})$. Here we assume that the nodes $s_{i}$
get these labels in advance as part of the contingent of “free” communication
that we budgeted for in Lemma 5.4 and which does not make the node
communication problem asymptotically easier.

In particular let $c_{1}>0$ be the constant from Lemma 5.4, such that we are
allowed $y=c_{1}k^{1+\delta}$ bits of free communication in total. This leaves
$c_{1}k^{\delta}$ bits for each of the $k$ labels
$\lambda(t_{1}),\dots,\lambda(t_{k})$. In the proof of Lemma 5.4 we chose
$k=c_{2}\cdot n^{\frac{2}{2+\delta}}\cdot\gamma^{\frac{1}{2+\delta}}$ (for
some constant $c_{2}>0$), resulting in a label size of at most
$c_{1}c_{2}\cdot
n^{\frac{2\delta}{2+\delta}}\cdot\gamma^{\frac{\delta}{2+\delta}}$. ∎

It remains to insert graphs $G\in\mathcal{G}_{k,\ell}$ into Lemma 5.5. We aim
for graphs $G=(V,E)\in\mathcal{G}_{k,\ell}$ with
$|E|\in\Theta\big{(}k^{1+\delta}\big{)}$ that maximize both girth $\ell$ and
density parameter $\delta$. As outlined in Appendix C, these are opposing
objectives, and for even girth $\ell\geq 4$ we know that
$\delta\in\smash{O}\big{(}\frac{2}{\ell-2}\big{)}$ (from applying Lemma C.2 on
uneven girth $\ell-1$). Bipartite graphs of girth $\ell$ that reach
$\delta\in\Theta\big{(}\frac{2}{\ell-2}\big{)}$ can be constructed for small
girth $\ell$ (summarized in Lemma C.6) from which we obtain Theorem 5.6. But
for higher girth we have to settle for $\delta$ below this threshold (see
Lemma C.7), this is reflected in Theorem 5.7.

###### Theorem 5.6.

Any algorithm that solves the _distance oracle problem_ in the
$\mathsf{HYBRID}(\infty,\gamma)$ model with constant success probability with

  * •

stretch $3\\!-\\!\varepsilon$ takes
$\Omega\big{(}(\tfrac{n}{\gamma})^{\frac{1}{3}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{3}}$

  * •

stretch $5\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/5}}{\gamma^{2/5}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{5}}$

  * •

stretch $7\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/7}}{\gamma^{3/7}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{7}}$

  * •

stretch $11\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/11}}{\gamma^{5/11}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{11}}$

for any const. $\varepsilon>0$ and a fixed const. $c>0$.

###### Proof.

By Lemma C.6 there are bipartite, balanced graphs with girth
$\ell\in\\{4,6,8,12\\}$ and $\Theta(n^{1+\frac{2}{\ell-2}})$ edges, thus
$\delta(\ell)=\frac{2}{\ell-2}$. In particular, we have
$\delta(4)=1,\delta(6)=\frac{1}{2},\delta(8)=\frac{1}{3},\delta(12)=\frac{1}{5}$,
which yield the desired results when plugged into Lemma 5.5. ∎

Applying Lemma 5.5 on the densest known graphs with larger girth (see Lemma
C.7), we obtain the subsequent theorem. The parametrization is complex due to
a case distinction in Lemma C.7, the upshot is that for any constant stretch
and sufficiently small $\gamma$ we get lower bounds polynomial in $n$ for
label up to sizes that are also polynomial.

###### Theorem 5.7.

Any algorithm that solves the _distance oracle problem_ in the
$\mathsf{HYBRID}(\infty,\gamma)$ model with constant success probability with

  * •

stretch $\ell\\!-\\!1\\!-\\!\varepsilon$ for $\ell\geq 14$ with $\ell\equiv
2\\!\\!\mod 4$ takes
$\Omega\Big{(}n^{\tfrac{2}{3\ell-8}}/\gamma^{\tfrac{3\ell-10}{6\ell-6}}\Big{)}$
rounds for label size $\leq c\cdot
n^{{4}/(3\ell-8)}\cdot\gamma^{{2}/(3\ell-8)}$

  * •

stretch $\ell\\!-\\!1\\!-\\!\varepsilon$ for $\ell\geq 16$ with $\ell\equiv
0\\!\\!\mod 4$ takes
$\Omega\Big{(}n^{\tfrac{2}{3\ell-10}}/\gamma^{\tfrac{3\ell-12}{6\ell-8}}\Big{)}$
rounds for label size $\leq c\cdot
n^{{4}/(3\ell-10)}\cdot\gamma^{{2}/(3\ell-10)}$

for any const. $\varepsilon>0$ and a fixed const. $c>0$.

###### Proof.

By Lemma C.7 there are bipartite, balanced graphs with even girth $\ell\geq
14$ that have (i) $\Theta(n^{1+\frac{4}{3\ell-10}})$ edges if $\ell\equiv
2\\!\\!\mod 4$, or (ii) $\Theta(n^{1+\frac{4}{3\ell-12}})$ edges if
$\ell\equiv 0\\!\\!\mod 4$. Thus in case (i) we have
$\delta(\ell)=\frac{4}{3\ell-10}$ and in case (ii)
$\delta(\ell)=\frac{4}{3\ell-12}$. Plugging $\delta(\ell)$ into Lemma 5.5
gives the desired result. ∎

###  5.3. Stateless Routing Scheme

For lower bounds of routing schemes we exploit the observation that for an
edge $e=\\{s_{i},t_{j}\\}\in E$ the node $s_{i}$ learns about the existence of
$e$ in $\Gamma$, i.e., whether $x_{e}=0$ or $x_{e}=1$, from the decision to
send a packet with destination $t_{j}$ first to $v$ or not. More precisely,
our goal is to show that $x_{e}=0$ if and only if $v$ is the first routing
neighbor for the packet with destination $t_{j}$.

However, we have to decrease the stretch of our lower bound in order that this
works. The main obstacle is that the decision of $s_{i}$ to send a packet with
target $t_{j}$ directly towards $u_{i}$ instead of node $v$ (left path) does
not impact the distance of the routing path that one can still obtain by that
much.

In particular, in the case of stateless routing, a packet that travels from
$s_{i}$ to $u_{i}$ and finds that the direct edge $\\{u_{i},t_{j}\\}$ does not
exist, could still use any other edge $\\{u_{i},t_{p}\\}$ and then the two
edges $\\{t_{p},v^{\prime}\\},\\{v^{\prime},t_{j}\\}$ to get to $t_{j}$ (e.g.,
in Figure 2 from $s_{2}$ to $t_{3}$). This would mislead $s_{i}$ as the first
routing node was not $v$, yet $x_{e}=0$.

The target is to prohibit this and some other troublesome routing options by
making them exceed the stretch guarantee. However, this gives us additional
restrictions that dominate the resulting system of inequalities for higher
girth $\ell$ of $G$, in particular we gain no improvement in the stretch for
$\ell\geq 8$.

###### Lemma 5.8.

Consider $\Gamma$ constructed from $G=(A,E)\in\mathcal{G}_{k,\ell}$ with
$|E|=\Theta\big{(}k^{1+\delta}\big{)}$ edges for some $\delta>0$. For any
constant $\varepsilon>0$ let
$\alpha_{\ell}=\sqrt{\ell\\!-\\!1}\\!-\\!\varepsilon$ for $\ell\leq 6$ and
$\alpha_{\ell}=1\\!+\\!\sqrt{2}\\!-\\!\varepsilon$ for $\ell\geq 8$. Any
algorithm that computes a _stateless routing scheme_ on $\Gamma$ with stretch
$\alpha_{\ell}$ and constant success probability in the
$\mathsf{HYBRID}(\infty,\gamma)$ model takes
$\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$
rounds. This holds for labels of size $c\cdot
n^{\frac{2\delta}{2+\delta}}\gamma^{\frac{\delta}{2+\delta}}$ and fixed
constant $c>0$.

###### Proof.

We set $w_{2}=1$ (this weight only plays a role later stateful routing lower
bound) and $w_{1}<w_{0}<(\ell\\!-\\!1)w_{1}$ (more precise values are
determined further below). Let $s_{i},t_{j}$ be a source-target pair of
$\Gamma$ where $e:=\\{s_{i},t_{j}\\}\in E$ is part of $G$ (but not necessarily
$\Gamma$). For the case $x_{e}=1$ we define
$d_{1}:=d(s_{i},t_{j})=w_{1}\\!+\\!h$ and
$d_{0}:=d(s_{i},t_{j})=w_{0}\\!+\\!h$ for the case $x_{e}=0$ (c.f., Lemma
5.3).

Let $\mathcal{A}$ be an algorithm solving the stateless routing problem with
the claimed approximation ratio (with const. probability). Let $P$ be the
simple $s_{i}$-$t_{j}$-path induced by the stateless routing scheme computed
by $\mathcal{A}$. Recall that $P$ must be simple as otherwise a packet that is
oblivious to the prior routing decisions would be trapped in a loop. Our aim
is that $s_{i}$ can decide whether $x_{e}=0$ or $x_{e}=1$ from the next
routing node on $P$. That is, we want that $P$ contains $v$ if and only if
$x_{e}=0$. However, there are a few options to obtain the $s_{i}$-$t_{j}$-path
$P$ that do, in certain cases, not abide by this requirement. We enumerate
these in the following.

Assume $P$ does not contain $e$. Then option (1) is to go the left “lane” via
$v$ and then use the direct blue edge $\\{v^{\prime},t_{j}\\}$ to get to
$t_{j}$, i.e., the path of length $d_{0}$. If $P$ goes from $s_{i}$ directly
to $u_{i}$, then $P$ can be completed into a path to $t_{j}$ by (2) using only
edges that are also part of $G$ (but not $e$), i.e., only red edges in Figure
2. Note that option (2) must include at least $\ell\\!-\\!1$ red edges due to
the girth $\ell$ of $G$. Option (3) is where $P$ goes to $u_{i}$ first uses
any red edge $\\{u_{i},t_{p}\\}$ ($p\neq j$) and then the two blue edges
$\\{t_{p},v^{\prime}\\},\\{v^{\prime},t_{j}\\}$ to reach $t_{j}$. Note that
for the case $x_{e}=0$ all other $s_{i}$-$t_{j}$-paths are either strictly
longer than option (1),(2),(3) or not simple. The distances of the three paths
(1),(2),(3) are at least (recall $w_{2}=1$):

$\displaystyle d^{(1)}$ $\displaystyle:=w_{0}+h\;(=d_{0})$ $\displaystyle
d^{(2)}$ $\displaystyle:=(\ell\\!-\\!1)w_{1}+h$ $\displaystyle d^{(3)}$
$\displaystyle:=w_{1}+2w_{0}+h$

To enforce $v\notin P$ in case $x_{e}=1$, we require that path (1) is
unfeasible, i.e., exceeds the allowed distance $\alpha_{\ell}d_{1}$.
Furthermore, to enforce $v\in P$ in case $x_{e}=0$, we require that the paths
(2) and (3) exceed the allowed distance $\alpha_{\ell}d_{0}$. From this we
obtain the following conditions.

(1) $\displaystyle\alpha_{\ell}\cdot d_{1}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(1)}=w_{0}+h$ (2)
$\displaystyle\alpha_{\ell}\cdot d_{0}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(2)}=(\ell\\!-\\!1)w_{1}+h$
(3) $\displaystyle\alpha_{\ell}\cdot d_{0}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(3)}=w_{1}+2w_{0}+h$

The remaining part of the proof is merely technical, we need to maximize
$\alpha_{\ell}$ under the above constraints. (Afterwards, the rest follows
from having solved the node communication problem as in the proof of Lemma
5.5). Set $w_{1}:=t<w_{0}$ for some yet unspecified variable $t>0$. Further,
we set $\alpha:=\frac{w_{0}}{t}-\varepsilon$ and show that this fulfills
Equation (1):

$\alpha_{\ell}\cdot
d_{1}=\big{(}\tfrac{w_{0}}{t}-\varepsilon\big{)}(t+h)=w_{0}+\tfrac{hw_{0}}{t}-\varepsilon(t+h)<w_{0}+h.$

For Equation (2) we obtain:

$\displaystyle\alpha_{\ell}\cdot
d_{0}=\big{(}\tfrac{w_{0}}{t}\\!-\\!\varepsilon\big{)}(w_{0}\\!+\\!h)<(\ell\\!-\\!1)t+h$
$\displaystyle\Longleftrightarrow\quad$
$\displaystyle\tfrac{w_{0}^{2}}{t}+\tfrac{w_{0}}{t}(h-\varepsilon
t)-\varepsilon h-h<(\ell\\!-\\!1)t$ $\displaystyle\Longleftrightarrow\quad$
$\displaystyle w_{0}^{2}+\underbrace{w_{0}(h-\varepsilon t)}_{<0,\text{ for
}t>h/\varepsilon}\underbrace{-\varepsilon ht-ht}_{<0}<(\ell\\!-\\!1)t^{2}$
$\displaystyle{\Longleftarrow}\quad$ $\displaystyle
w_{0}^{2}\leq(\ell\\!-\\!1)t^{2}$ $\displaystyle{\Longleftrightarrow}\quad$
$\displaystyle w_{0}\leq t\cdot\sqrt{\ell\\!-\\!1}.$

Now let us turn to Equation (3)

$\displaystyle\alpha_{\ell}\cdot
d_{0}=\big{(}\tfrac{w_{0}}{t}\\!-\\!\varepsilon\big{)}(w_{0}\\!+\\!h)<t+2w_{0}+h$
$\displaystyle\Longleftrightarrow\quad$
$\displaystyle\tfrac{w_{0}^{2}}{t}+\tfrac{w_{0}}{t}(h-\varepsilon
t)-\varepsilon h<t+2w_{0}+h$ $\displaystyle\Longleftrightarrow\quad$
$\displaystyle w_{0}^{2}+w_{0}(\underbrace{h-\varepsilon
t}_{<0}-2t)\underbrace{-\varepsilon ht-ht}_{<0}-t^{2}<0$
$\displaystyle\Longleftarrow\quad$ $\displaystyle w_{0}^{2}-2tw_{0}-t^{2}\leq
0$ $\displaystyle\Longleftarrow\quad$ $\displaystyle w_{0}\leq
t\cdot(1\\!+\\!\sqrt{2}).$

Therefore, Equations (2),(3) are fulfilled if $w_{0}\leq
t\cdot\sqrt{\ell\\!-\\!1}$ and $w_{0}\leq t\cdot(1\\!+\\!\sqrt{2})$ (and
$t>\frac{h}{\varepsilon}$, which can be chosen freely). This implies that the
stretch $\alpha_{\ell}=\frac{w_{0}}{t}-\varepsilon$ must satisfy
$\alpha_{\ell}\leq\sqrt{\ell\\!-\\!1}-\varepsilon$ and $\alpha_{\ell}\leq
1\\!+\\!\sqrt{2}\\!-\\!\varepsilon$, whereas the former condition for
$\alpha_{\ell}$ dominates the latter if and only if $\ell\leq 8$.

With this choice of $w_{0},\alpha_{\ell}$, the first node that a packet from
$s_{i}$ with destination $t_{j}$ is routed to is the node $v$ if and only if
$x_{e}=0$. Hence, the nodes in $B$ collectively learn $X$ from the information
provided by algorithm $\mathcal{A}$ and the labels of the nodes $t_{j}$, which
therefore solves the node communication problem. The runtime and size of the
labels then follows the same way as in the proof of Lemma 5.5. ∎

We plug graphs $G\in\mathcal{G}_{k,\ell}$ into Lemma 5.8. Since in this case
we get no improvements in the stretch for girth $\ell\geq 8$ it suffices to
apply Lemma C.6. Beside the changed values for the stretch, the proof is the
same as that of Theorem 5.6, we just have to use the corresponding values of
$\delta$ from Lemma C.6 for $\ell=4,6,8$.

###### Theorem 5.9.

Any algorithm that solves the _stateless routing problem_ in the
$\mathsf{HYBRID}(\infty,\gamma)$ model with constant success probability with

  * •

stretch $\sqrt{3}\\!-\\!\varepsilon$ takes
$\Omega\big{(}(\tfrac{n}{\gamma})^{\frac{1}{3}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{3}}$

  * •

stretch $\sqrt{5}\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/5}}{\gamma^{2/5}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{5}}$

  * •

stretch $1\\!+\\!\sqrt{2}\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/7}}{\gamma^{3/7}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{7}}$

for any const. $\varepsilon>0$ and a fixed const. $c>0$.

###  5.4. Stateful Routing Scheme

We obtain similar lower bound results for the approximate stateful routing
problem, however with even smaller stretch. Recall that in the stateful
version the problem is relaxed in the sense that a routing decision may also
depend on the information a packet has gathered along the previous routing
path.

Since this permits loops in the routing path, it opens up additional options
for routing a packet from $s_{i}$ to $t_{j}$ that we need to prohibit. For
instance, a packet could first travel to $u_{i}$, then check if the direct
edge $\\{u_{i},t_{j}\\}$ is present, and if not travel back to $s_{i}$ to take
the shorter route via $v$ instead. Note that this path has the same number of
red and blue edges as the shortest path directly to $v$ and then to $t_{j}$
(c.f. Figure 2).

The trick is to make the weight $w_{2}$ (orange edges) of all incident edges
of $s_{i}$ more expensive, such that revisiting $s_{i}$ breaks the
approximation guarantee. This again forces the source $s_{i}$ to make the
correct decision with the first node it routes the packet to, which renders
the ability to travel in loops and learn along the way useless.

###### Lemma 5.10.

Consider $\Gamma$ constructed from $G=(A,E)\in\mathcal{G}_{k,\ell}$ with
$|E|=\Theta\big{(}k^{1+\delta}\big{)}$ edges for some $\delta>0$. For any
constant $\varepsilon>0$ let $\alpha_{4}=\sqrt{2}-\varepsilon$,
$\alpha_{6}=\tfrac{5}{3}-\varepsilon$, $\alpha_{8}=\tfrac{7}{4}-\varepsilon$.
For $\ell\geq 10$ let $\alpha_{\ell}=\frac{3+\sqrt{17}}{4}-\varepsilon\approx
1.78$. Any algorithm that computes a _stateful routing scheme_ on $\Gamma$
with stretch $\alpha_{\ell}$ and constant success probability in the
$\mathsf{HYBRID}(\infty,\gamma)$ model takes
$\Omega\big{(}(\tfrac{n^{\delta}}{\gamma})^{\frac{1}{2+\delta}}\big{)}$
rounds. This holds for labels of size
$c\\!\cdot\\!n^{\frac{2\delta}{2+\delta}}\\!\cdot\\!\gamma^{\frac{\delta}{2+\delta}}$
and fixed constant $c>0$.

###### Proof.

The beginning of the proof is similar to the one of Lemma 5.8. Consider
algorithm $\mathcal{A}$ that solves the stateful routing problem with the
claimed approximation ratio and constant probability. Let $s_{i},t_{j}\in
V_{\Gamma}$ with $e:=\\{s_{i},t_{j}\\}\in E$ and define
$d_{1}:=d(s_{i},t_{j})=w_{1}\\!+\\!w_{2}\\!+\\!h\\!-\\!1$ and
$d_{0}:=d(s_{i},t_{j})=w_{0}\\!+\\!w_{2}\\!+\\!h\\!-\\!1$ for the cases
$x_{e}=1$, $x_{e}=0$ respectively (we will ensure
$w_{1}<w_{0}<(\ell\\!-\\!1)w_{1}$ so that Lemma 5.3 applies).

Let $P$ be the $s_{i}$-$t_{j}$-path induced by the stateful routing scheme
computed by $\mathcal{A}$. Similar to before, our goal is to show that the
first node on $P$ is $v$ if and only if $x_{e}=0$, so that $s_{i}$ learns
$x_{e}$ from its routing decision. As before, we aim to prohibit all routing
options (i.e., make them break the stretch guarantee) that do not abide by
this requirement. We will extend our list of options for $P$ which are in some
cases undesirable from the previous proof.

We have the loop-less routing options (1),(2),(3) from before (c.f., proof of
Lemma 5.8), whose lengths change by an additive term $w_{2}-1$ due to the
introduction of weight $w_{2}$ (orange edges in Figure 2). Note that any path
(possibly with loops) that contains $s_{i}$ just once is at least as long as
one of the options (1)-(3) (in their respective cases) so prohibiting the
latter prohibits the former.

The problem that arises is from visiting $s_{i}$ at least twice is that it can
mislead $s_{i}$ by first going to $v$ even though $x_{e}=1$ or vice versa.
Assume the case that $e$ is not in $\Gamma$ ($x_{e}=0$), then we need to
prohibit routing option (4) that visits the first node on the path towards
$u_{i}$, returns to $s_{i}$, travels directly to $v^{\prime}$ and uses the
blue edge to $t_{j}$. Conversely, assuming the case that $e$ is present in
$\Gamma$ ($x_{e}=1$), $P$ we need to prohibit option (5), which visits $v$
first but then returns to $s_{i}$, travels to $u_{i}$ and uses $e$ to reach
$t_{j}$. Note that all paths that contain $s_{i}$ at least twice, are at least
as long as one of the paths (4),(5) (in their respective cases). The described
routing paths (1)-(5) have the following respective lengths:

$\displaystyle d^{(1)}$ $\displaystyle:=w_{0}+w_{2}+h-1$ $\displaystyle
d^{(2)}$ $\displaystyle:=(\ell\\!-\\!1)w_{1}+w_{2}+h-1$ $\displaystyle
d^{(3)}$ $\displaystyle:=2w_{0}+w_{1}+w_{2}+h-1$ $\displaystyle d^{(4)}$
$\displaystyle:=w_{0}+3w_{2}+h-1$ $\displaystyle d^{(5)}$
$\displaystyle:=w_{1}+3w_{2}+h-1$

We obtain inequalities similar as before. For the reasoning of inequalities
(1)-(3) consider the proof of Lemma 5.8. Observe that if $P$ would follow path
options (4),(5) it could make $s_{i}$ believe $x_{e}=1$ or $x_{e}=0$
respectively, even though the opposite is true. We require that path options
(4) and (5) exceed the stretch $\alpha_{\ell}$ in the cases in which they are
undesirable, that is, $x_{e}=0$ and $x_{e}=1$, respectively.

(1) $\displaystyle\alpha_{\ell}\cdot d_{1}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(1)}=w_{0}+w_{2}+h-1$ (2)
$\displaystyle\alpha_{\ell}\cdot d_{0}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(2)}=(\ell\\!-\\!1)w_{1}+w_{2}+h-1$
(3) $\displaystyle\alpha_{\ell}\cdot d_{0}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(3)}=2w_{0}+w_{1}+w_{2}+h-1$
(4) $\displaystyle\alpha_{\ell}\cdot d_{0}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(4)}=w_{0}+3w_{2}+h-1$ (5)
$\displaystyle\alpha_{\ell}\cdot d_{1}$
$\displaystyle\stackrel{{\scriptstyle!}}{{<}}d^{(5)}=w_{1}+3w_{2}+h-1$

This leaves us with an optimization problem where $\alpha_{\ell}$ is to be
maximized in the domain $1\leq w_{1}\leq w_{0},w_{2}$, subject to conditions
(1)-(5). This is admittedly a bit tedious, in particular since the
optimization problem has a different result for girth $\ell\in\\{4,6,8,10\\}$
(we gain no improvement for larger $\ell$). We do not reproduce all necessary
calculations of the optimization in detail, instead we give some explanations
to make our results (given in Table 2) reproducible.

One obstacle is the presence of edges with weight 1 in $\Gamma$ forming the
path of length $h-1$, which is not yet fixed and therefore prohibits solving
the optimization problem directly. Our strategy is to first relax our problem
to a simplified one with zero-weight edges. That is, we set all edges, except
those with weight $w_{0},w_{1},w_{2}$, to zero and adapt the distances
$d_{0},d_{1},d^{(1)},\dots,d^{(5)}$ accordingly (essentially slashing
$h\\!-\\!1$ in those distances). We also set $w_{1}=1$. This eliminates
$w_{1},h$ from conditions (1)-(5) and the resulting maximization problem(s)
can be solved directly.

From the results of the simplified optimization problems (for girths
$\ell\in\\{4,6,8,10\\}$), we obtain almost optimal solutions for the general
optimization problem with non-zero weights as follows. We multiply the values
of $w_{0},w_{1},w_{2}$ with a (sufficiently large) parameter $t\geq 1$ and
subtract an $\varepsilon>0$ from $\alpha_{\ell}$ to accommodate a (small)
slack that is required in the general inequalities. The value of $t$ depends
on the slack $\varepsilon$ in $\alpha_{\ell}$ that is given but is generally
polynomial in $n$ as long as $\varepsilon$ is constant. The results obtained
using this procedure are given in Table 2.

$\ell$ |  $\alpha_{\ell}$ |  $w_{0}$ |  $w_{1}$ |  $w_{2}$
---|---|---|---|---
4 |  $\sqrt{2}-\varepsilon$ |  $2t\sqrt{2}\\!-\\!t$ |  $t$ |  $t$
6 |  $\frac{5}{3}-\varepsilon$ |  $\frac{5t}{2}$ |  $t$ |  $\frac{5t}{4}$
8 |  $\tfrac{7}{4}-\varepsilon$ |  $\frac{35t}{11}$ |  $t$ |  $\frac{21t}{11}$
10 |  $\frac{3+\sqrt{17}}{4}-\varepsilon$ |  $\frac{3+\sqrt{17}}{2}t$ |  $t$ |  $\frac{5+\sqrt{17}}{4}t$
Table 2.  Results of maximizing $\alpha_{\ell}$, s.t., conditions (1)-(5) for
$\ell\in\\{4,6,8,10\\}$ (and scaling with $t$ and introducing slack
$\varepsilon$).

The most relevant parameter in Table 2 are certainly the values for
$\alpha_{\ell}$ for $\ell\in\\{4,6,8,10\\}$, whereas we also provide the
weights $w_{0},w_{1},w_{2}$ for reproducibility. Showing that the given
parameters do in fact satisfy conditions (1)-(5) for any constant
$\varepsilon>0$ and some choice of $t$, is a repetitive task. We show this
once for $\ell=10$ and condition (1) (which is almost tight in this case), the
other cases can be repeated analogously.

$\displaystyle\alpha_{\ell}\cdot d_{1}$
$\displaystyle=\big{(}\tfrac{3+\sqrt{17}}{4}\big{)}d_{1}-\varepsilon d_{1}$
$\displaystyle=\big{(}\tfrac{3+\sqrt{17}}{4}\big{)}(w_{1}+w_{2}+h-1)-\varepsilon
d_{1}$
$\displaystyle=\big{(}\tfrac{3+\sqrt{17}}{4}\big{)}(w_{1}+w_{2})+h\\!-\\!1+\smash{\underbrace{\big{(}\tfrac{\sqrt{17}-1}{4}\big{)}(h\\!-\\!1)-\varepsilon
d_{1}}_{<0,\text{ for large }t}}$
$\displaystyle<\big{(}\tfrac{3+\sqrt{17}}{4}\big{)}\big{(}\tfrac{9+\sqrt{17}}{4}\cdot
t\big{)}+h\\!-\\!1$ $\displaystyle=\big{(}\tfrac{11+3\sqrt{17}}{4}\big{)}\cdot
t+h\\!-\\!1$
$\displaystyle=\big{(}\tfrac{3+\sqrt{17}}{2}+\tfrac{5+\sqrt{17}}{4}\big{)}\cdot
t+h\\!-\\!1$ $\displaystyle=w_{0}+w_{2}+h\\!-\\!1=\smash{d^{(1)}}.$

Note that, since $d_{1}$ grows linear in $t$ the inequality in the fourth line
holds for
$t>\big{(}\tfrac{\sqrt{17}-1}{4\varepsilon}\big{)}(h\\!-\\!1)\in\smash{O}(n)$.

Finally, by enforcing conditions (1)-(5) with the appropriate parameters given
in Table 2, we can guarantee that the first node that a packet from $s_{i}$ to
$t_{j}$ is first routed to $v$ if and only if $x_{e}=0$. From this the nodes
in $B$ collectively learn $X=(x_{e})_{e\in E}$ thus solving the node
communication problem. The runtime and size of the labels follows as in the
proof of Lemma 5.5. ∎

Again, our actual lower bounds come from inserting graphs
$G\in\mathcal{G}_{k,\ell}$ into Lemma 5.8. Our best stretch is obtained for
$\ell=10$, but unfortunately we have a gap for that value in Lemma C.6.
Therefore, for the largest stretch value we use a graph
$G\in\mathcal{G}_{k,12}\subseteq\mathcal{G}_{k,10}$, which has the drawback of
not being as dense. Aside from different stretch values, the proof follows
that of Theorem 5.6, by inserting the values of $\delta$ from Lemma C.6 for
$\ell=4,6,8,12$.

###### Theorem 5.11.

Any algorithm that solves the _stateful routing problem_ in the
$\mathsf{HYBRID}(\infty,\gamma)$ model with constant success probability with

  * •

stretch $\sqrt{2}\\!-\\!\varepsilon$ takes
$\Omega\big{(}(\tfrac{n}{\gamma})^{\frac{1}{3}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{3}}$

  * •

stretch $\frac{5}{3}\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/5}}{\gamma^{2/5}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{5}}$

  * •

stretch $\frac{7}{4}\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/7}}{\gamma^{3/7}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{7}}$

  * •

stretch $\frac{3+\sqrt{17}}{4}\\!-\\!\varepsilon$ takes
$\Omega\big{(}\tfrac{n^{1/11}}{\gamma^{5/11}}\big{)}$ rounds for label size
$\leq c\cdot(n^{2}\gamma)^{\frac{1}{11}}$

for any const. $\varepsilon>0$ and a fixed const. $c>0$.

##  Appendix A Some Basic Probabilistic Concepts

###### Lemma A.1 (Chernoff Bound).

We use the following forms of Chernoff bounds in our proofs:

$\mathbb{P}\big{(}X>(1\\!+\\!\delta)\mu_{H}\big{)}\leq\exp\Big{(}\\!-\\!\frac{\delta\mu_{H}}{3}\Big{)},$

with $X=\sum_{i=1}^{n}X_{i}$ for i.i.d. random variables $X_{i}\in\\{0,1\\}$
and $\mathbb{E}(X)\leq\mu_{H}$ and $\delta\geq 1$. Similarly, for
$\mathbb{E}(X)\geq\mu_{L}$ and $0\leq\delta\leq 1$ we have

$\mathbb{P}\big{(}X<(1\\!-\\!\delta)\mu_{L}\big{)}\leq\exp\Big{(}\\!-\\!\frac{\delta^{2}\mu_{L}}{2}\Big{)}.$

###### Remark A.2.

Note that the first inequality even holds if we have $k$-wise independence
among the random variables $X_{i}$ for $k\geq\lceil\mu_{H}\delta\rceil$ (c.f.,
[28] Theorem 2, note that a substitution
$\mu_{H}:=(1\\!+\\!\varepsilon)\mathbb{E}(X)$ generalizes the result for any
$\mu_{H}\geq\mathbb{E}(X)$).

###### Lemma A.3 (Union Bound).

Let $E_{1},\ldots,E_{k}$ be events, each taking place w.h.p. If $k\leq p(n)$
for a polynomial $p$, then $E\coloneqq\bigcap_{i=1}^{k}E_{i}$ also takes place
w.h.p.

###### Proof.

Let $d\coloneqq\deg(p)\\!+\\!1$. Then there is an $n_{0}\geq 0$ such that
$p(n)\leq n^{d}$ for all $n\geq n_{0}$. Let $n_{1},\ldots,n_{k}\in\mathbb{N}$
such that for all $i\in\\{1,\ldots,k\\}$ we have
$\mathbb{P}(\overline{E_{i}})\leq\tfrac{1}{n^{c}}$ for some (yet unspecified)
$c>0$. With Boole’s Inequality (union bound):

$\displaystyle\mathbb{P}\big{(}\overline{E}\big{)}\\!=\mathbb{P}\Big{(}\bigcup_{i=1}^{k}\overline{E_{i}}\Big{)}\leq\sum_{i=1}^{k}\mathbb{P}(\overline{E_{i}})\leq\sum_{i=1}^{k}\\!\frac{1}{n^{c}}\leq\frac{p(n)}{n^{c}}\leq\frac{1}{n^{c-d}}$

for all $n\geq n_{0}^{\prime}\coloneqq\max(n_{0},\ldots,n_{k})$. Let
$c^{\prime}>0$ be arbitrary. We choose $c\geq c^{\prime}\\!\\!+\\!d$. Then
$\mathbb{P}\big{(}\overline{E}\big{)}\leq\frac{1}{n^{c^{\prime}}}$ for all
$n\geq n_{0}^{\prime}$. ∎

###### Remark A.4.

If a constant number of events is involved we use the above lemma without
explicitly mentioning it. It is possible to use the lemma in a nested fashion
as long as the number of (nested) applications is polynomial in $n$.

Our main application for the above two lemmas is the proof of Lemma 2.1.

###### Proof of Lemma 2.1.

Let $u,v\in V$ with $hop(u,v)\\!\geq\\!\xi x\ln n$. Fix a shortest
$u$-$v$-path $P_{u,v}$ and let $Q$ be a sub-path of $P_{u,v}$ with at least
$\xi x\ln n$ nodes. Let $X_{u,v}$ be the random number of marked nodes on $Q$.
Then we have $\mathbb{E}(X_{u,v})\geq\frac{|Q|}{x}\geq{\xi\ln n}$. Let $c>0$
be arbitrary. We use a Chernoff bound (c.f. Lemma A.1):

$\mathbb{P}\Big{(}X_{u,v}<\frac{\xi\ln
n}{2}\Big{)}\leq\exp\Big{(}\\!\\!-\\!\frac{\xi\ln
n}{8}\Big{)}\stackrel{{\scriptstyle\xi\geq 8c}}{{\leq}}\frac{1}{n^{c}}.$

Thus we have $X_{u,v}\geq 1$ w.h.p. for constant $\xi\geq\max(8c,2/\ln n)$.
Therefore the claim holds w.h.p. for the pair $u,v$. We claim that w.h.p. the
event $X_{u,v}\geq 1$ occurs for all pairs $u,v\in V$ and for all sub-paths
$Q$ of $P_{u,v}$ longer than $\xi x\ln n$ hops, for at least one shortest path
$P_{u,v}$ from $u$ to $v$. There are at most $n^{2}$ many pairs $u,v\in V$.
Moreover we can select at most $n$ sub-paths $Q$ of $P$ that do not fully
contain any other selected sub-path. Hence the claim follows with the union
bound given in Lemma A.3. ∎

##  Appendix B Concepts from Information Theory

The Entropy $H(X)\\!:=\\!-\\!\sum_{x\in
S}\mathbb{P}(X\\!=\\!x)\log\big{(}\mathbb{P}(X\\!=\\!x)\big{)}$ gives a lower
bound for expected number of bits required for encoding the state of a random
variable. This is entailed by Shannon’s [25] source coding theorem.

###### Lemma B.1 (c.f., [25]).

Given a random variable $X$ with outcomes from some set $S$ and an uniquely
decodable code $f:S\to\\{0,1\\}^{*}$ with expected code length
$\mathbb{E}(|f(X)|)$. Then $\mathbb{E}(|f(X)|)\geq H(X)$.

In particular, in a two party communication setting (see Definition 3.2) this
implies that $H(X)$ constitutes a lower bound for the worst case number of
bits that have to be transmitted from one party that knows the state of $X$ to
some party that needs to learn it.

###### Corollary B.2.

Bob must receive at least $H(X)$ bits from Alice in expectation, as part of
any protocol solving the two party communication problem (Def. 3.2).

###### Proof.

Assume, for a contradiction, that we have a protocol $\mathcal{P}$ in which
sending less than $H(X)$ bits from Alice to Bob always suffices to solve the
two party communication problem. Clearly, for any two possible outcomes
$x_{1},x_{2}\in S$ of $X$, the transcript of the communication occurring
between Alice and Bob must be different as otherwise Bob would not be able to
distinguish $x_{1}$ from $x_{2}$. But then we could use the transcript of
$\mathcal{P}$ for any given outcome of $x\in S$ of $X$ as uniquely decodable
code for $x$ of expected length less than $H(X)$, a contradiction to Lemma
B.1. ∎

Using information theoretic concepts, the above statement generalizes for a
protocol that has a probability of at least $p$ that Bob can successfully
decode the state of $X$ after it is terminates.

###### Lemma B.3.

Bob must receive at least $p\cdot H(X)-1$ bits from Alice in expectation, as
part of any protocol that solves the two party communication problem (c.f.,
Def. 3.2) with probability at least $p$.

###### Proof.

We assume that the random variable $X$ has a finite number of outcomes (which
is sufficient for our purposes), i.e., $X\in\\{x_{1},\dots,x_{k}\\}$ for some
$k\in\mathbb{N}$. Assuming the outcome $X=x_{i}$, let $y_{i}$ be the output
that Bob makes after the randomized communication protocol terminates. Then

$\displaystyle y_{i}=\begin{cases}x_{i},&\text{with probability }p_{i}\\\
x_{j}\text{ and }j\neq i,&\text{with probability }(1-p_{i}),\end{cases}$

where $p\leq p_{i}\leq 1$. That means we have another random variable $Y$
dependent on $X$, which describes Bob’s guess about the state of $X$. It
remains to prove that the information about $X$ that is still contained in
$Y$, is large. This is known as the transinformation $I(X;Y)$ and since Bob
“learns” the state of $Y$, at least $I(X;Y)$ must have been transmitted from
Alice to Bob. In particular, we want to show $I(X;Y)\geq p\cdot H(X)-1$. The
transinformation is defined as

$I(X;Y)=\sum_{i,j\in[k]}\mathbb{P}(X\\!=\\!x_{i},Y\\!=\\!x_{j})\cdot\log\frac{\mathbb{P}(X\\!=\\!x_{i},Y\\!=\\!x_{j})}{\mathbb{P}(X\\!=\\!x_{i})\mathbb{P}(Y\\!=\\!x_{j})}$

Analyzing this directly is tricky since the output distribution of $Y$ for the
second case, where $Y\neq X$, is not specified (and can not be made such,
without loosing the generality of the claim). So we have to take a detour by
defining a third random variable $Z$ that tells us if the protocol was
successful.

$\displaystyle Z=\begin{cases}1,&\text{if }y_{i}=x_{i}\\\
0,&\text{else}.\end{cases}$

To simplify the analysis of the transinformation we assume that Bob gets to
know $Z$ “for free” and since $H(Z)\leq 1$ the additional information about
$X$ from learning $Y$ is not significantly reduced. Formally, we first show
$I(X;Y)\geq I(X;Y,Z)-H(Z)$ which allows us to analyze $I(X;Y,Z)$ instead.

The conditional entropy $H(A|B)$ describes the amount of “new” information in
some random variable $A$ given that we already know random variable $B$. In
the following steps we will use the fact that $H(Z|X,Y)=0$ since $Z$ is
functionally dependent on $X$ and $Y$ and we will the chain rule of entropy
$H(A,B)=H(A|B)\\!+\\!H(B)$. We plug this into the alternative characterization
of transinformation

def. of $I(X;Y,Z)$ $\displaystyle I(X;Y,Z)$ $\displaystyle=H(X)-H(X|Y,Z)$
chain rule $\displaystyle=H(X)-H(X,Z|Y)+H(Z|Y)$ chain rule
$\displaystyle=H(X)-H(Z|X,Y)-H(X|Y)+H(Z|Y)$ $H(Z|X,Y)=0$
$\displaystyle=H(X)-H(X|Y)+H(Z|Y)$ def. of $I(X;Y)$
$\displaystyle=I(X;Y)+H(Z|Y)$ $\displaystyle\leq I(X;Y)+H(Z).$

This implies $I(X;Y)\geq I(X;Y,Z)-H(Z)$, and it remains to show that
$I(X;Y,Z)$ is large. The random variable $Z$ helps in the following way. For
any $x_{i}$ we have

$\mathbb{P}(Y\\!\\!=\\!\\!x_{i},Z\\!\\!=\\!\\!1)=p_{i}\cdot\mathbb{P}(X\\!\\!=\\!\\!x_{i})=\mathbb{P}(X\\!\\!=\\!\\!x_{i},Y\\!\\!=\\!\\!x_{i},Z\\!\\!=\\!\\!1),$

since $Z=1$ means that $Y=x_{i}$ is only possible if $X=x_{i}$. We obtain

$\displaystyle I(X;Y,Z)$
$\displaystyle=\sum_{i,j\in[k],z\in\\{0,1\\}}\mathbb{P}(X\\!\\!=\\!\\!x_{i},Y\\!\\!=\\!\\!x_{j},Z\\!\\!=\\!\\!z)\cdot\log\frac{\mathbb{P}(X\\!\\!=\\!\\!x_{i},Y\\!\\!=\\!\\!x_{j},Z\\!\\!=\\!\\!z)}{\mathbb{P}(X\\!\\!=\\!\\!x_{i})\cdot\mathbb{P}(Y\\!\\!=\\!\\!x_{j},Z\\!\\!=\\!\\!z)}$
$\displaystyle\geq\sum_{i\in[k]}\mathbb{P}(X\\!\\!=\\!\\!x_{i},Y\\!\\!=\\!\\!x_{i},Z\\!\\!=\\!\\!1)\cdot\log\frac{\mathbb{P}(X\\!\\!=\\!\\!x_{i},Y\\!\\!=\\!\\!x_{i},Z\\!\\!=\\!\\!1)}{\mathbb{P}(X\\!\\!=\\!\\!x_{i})\cdot\mathbb{P}(Y\\!\\!=\\!\\!x_{i},Z\\!\\!=\\!\\!1)}$
$\displaystyle=\sum_{i\in[k]}p_{i}\cdot\mathbb{P}(X\\!\\!=\\!\\!x_{i})\cdot\log\frac{1}{\mathbb{P}(X\\!\\!=\\!\\!x_{i})}$
$\displaystyle\geq\>p\cdot\sum_{i\in[k]}\mathbb{P}(X\\!\\!=\\!\\!x_{i})\cdot\log\frac{1}{\mathbb{P}(X\\!\\!=\\!\\!x_{i})}=p\cdot
H(X)$

Finally, we have $I(X;Y)\geq I(X;Y,Z)-H(Z)\geq p\cdot H(X)-1.$ ∎

##  Appendix C Density of Bounded Girth Graphs

We reproduce a few known and conjectured results from extremal graph theory,
in particular that the number of edges in cycle-free graphs can be bounded
from above and below. We are going to formulate these results in the context
and granularity that we require in this article (neglecting constants, in
particular). First, there is a long standing conjecture from Erdős and
Simonovits [14].292929[14] states in Conjecture 5 that there are graphs
without cycles of a fixed length with the claimed density, and conjectures
that the same holds for excluding smaller cycles as well (below Theorem 2 of
[14]).

###### Corollary C.1 (by [14]).

For any $k\\!\in\\!\mathbb{N}$, there is an $n$-node graph with girth $\geq
2k\\!+\\!1$ and $\Theta(n^{1+\frac{1}{k}})$ edges.

It is known that a graph with average degree $d$ and girth $2k+1$ has
$n\in\Omega(d^{k})$ nodes due to [6]. This translates into the following
lemma:

###### Lemma C.2 (c.f., [6]).

Any $n$-node graph with girth at least $2k+1,k\in\mathbb{N}$ has at most
$O(n^{1+\frac{1}{k}})$ edges.

Conjecture C.1 is known to be true for some parameters of $k$ due to [27] and
[9].

###### Lemma C.3 (c.f., [27], [9]).

For $k=2,3,5$ there are $n$-node graphs with girth $2k\\!+\\!1$ and
$\Theta(n^{1+\frac{1}{k}})$ edges.

There are more general lower bounds for graphs for arbitrary girth by [22]
which the survey [31] summarizes as follows:

###### Lemma C.4 (c.f., [22], [31]).

For any $k\geq 2$ there is a $n$-node graph with girth $2k\\!+\\!1$ and
$\Theta(n^{1+\frac{2}{3k-2}})$ edges if $k$ is even, and
$\Theta(n^{1+\frac{2}{3k-3}})$ if $k$ is odd.

Above we mention only uneven girth, whereas in this paper we are mostly
interested in (balanced) bipartite graphs which naturally have even girth.
Note that given a graph with girth $2k+1$, one easily obtains a balanced,
bipartite graph of even girth $2k+2$ with the same asymptotic order and size
by constructing the bipartite double cover.

###### Lemma C.5.

Let $G\\!=\\!(V,E)$ be a $n$-node graph with girth $2k\\!+\\!1$, then there is
a balanced, bipartite graph $G^{\prime}\\!=\\!(V^{\prime},E^{\prime})$ with
girth $2k\\!+\\!2$, $|V^{\prime}|\\!=\\!2|V|$ and $|E^{\prime}|\\!=\\!2|E|$.

###### Proof.

Let $V^{\prime}:=\bigcup_{v\in V}\\{v_{1},v_{2}\\}$, i.e., for each node $v\in
V$ we create two copies. Further, let $E^{\prime}=\bigcup_{\\{u,v\\}\in
E}\\{\\{u_{1},v_{2}\\},\\{v_{1},u_{2}\\}\\}$, i.e., for each edge $\\{u,v\\}$
in $E$ we create two “crossing” edges between the node copies $u_{1},v_{2}$
and $u_{2},v_{1}$. Any cycle of $G^{\prime}$ must form a corresponding cycle
in $G$, by taking the original edge $\\{u,v\\}$ for each edge
$\\{u_{1},v_{2}\\}$ in that cycle. Thus $G^{\prime}$ can not have a cycle
shorter than $2k+1$. Further, by construction, we have a (balanced)
bipartition of $G^{\prime}$ given by the nodes with index $1$ and $2$,
respectively. Since $G^{\prime}$ is bipartite, it can not contain an odd
cycle, hence the girth is at least $2k+2$. ∎

Combining Lemma C.5 with Lemma C.3 and the $n$-node clique which has girth 3
and $\Theta(n^{2})$ edges, we obtain the following lemma.

###### Lemma C.6.

For $\ell=4,6,8,12$ there are balanced, bipartite $n$-node graphs with girth
$\ell$ and $\Theta(n^{1+\frac{2}{\ell-2}})$ edges.

Note that Lemma C.6 this is tight, since for any even $\ell\geq 4$ we obtain
the upper bounds $\Omega(n^{1+\frac{2}{\ell-2}})$ in Lemma C.2 by plugging in
the smaller uneven girth $\ell-1$. For all other even girths we have to fall