# Parallel Greedy Spanners

Bernhard Haeupler D Ellis Hershkowitz Zihan Tan ETH Zürich & ETH Zürich
DIMACS, Carnegie Mellon University Rutgers University

###### Abstract

A $t$-spanner of a graph is a subgraph that $t$-approximates pairwise
distances. The greedy algorithm is one of the simplest and most well-studied
algorithms for constructing a sparse spanner: it computes a $t$-spanner with
$n^{1+O(1/t)}$ edges by repeatedly choosing any edge which does not close a
cycle of chosen edges with $t+1$ or fewer edges.

We demonstrate that the greedy algorithm computes a $t$-spanner with
$t^{3}\cdot\log^{3}n\cdot n^{1+O(1/t)}$ edges _even when a matching of such
edges are added in parallel_. In particular, it suffices to repeatedly add any
matching where each individual edge does not close a cycle with $t+1$ or fewer
edges but where adding the entire matching might. Our analysis makes use of
and illustrates the power of new advances in length-constrained expander
decompositions.

##  1 Introduction

A spanner of a graph is a sparse subgraph that approximately preserves
pairwise distances.

######  Definition 1 ($t$-Spanner).

Given graph $G=(V,E)$ and $t\geq 1$, a $t$-spanner is a subgraph
$H=(V,E^{\prime})$ of $G$ such that for every $u,v\in V$ we have

$\displaystyle d_{H}(u,v)\leq t\cdot d_{G}(u,v).$

(See Section 2 for standard notation and definitions). Since their
formalization by [30], spanners have become indispensable in graph
sparsfication and graph algorithms. For example, they have found applications
in distributed broadcast [1, 5], network synchronization [4, 31, 1, 5, 28],
overlay, sensor and wireless networks [10, 39, 25, 38, 11, 35], VLSI circuit
design [12, 13, 34], routing [40, 36], distance oracles [37, 29, 32] and
approximate shortest paths [15, 33, 16, 18, 19]. Generally speaking, these
works make use of sparse spanners; namely, spanners with a small number of
edges.

One of the simplest and most well-studied ways of computing a sparse
$t$-spanner $H$ is the greedy algorithm. The greedy algorithm is based on what
we will call _unspanned edges_.

######  Definition 2 (Unspanned Edge).

Given graph $G=(V,E)$ and subgraph $H\subseteq G$, say that edge $\\{u,v\\}\in
E$ is $t$-unspanned with respect to $H\subseteq G$ if $d_{H}(u,v)>t$.

In other words, $\\{u,v\\}$ is $t$-unspanned with respect to $H$ if it does
not close a $(t+1)$-cycle in $H$. To compute a $t$-spanner $H$, the greedy
algorithm simply repeatedly adds $t$-unspanned edges to $H$ until none exist;
see Algorithm 1.

Algorithm 1 Sequential Greedy Algorithm for $t$-Spanners

Input: Graph $G=(V,E)$ and $t\geq 1$

Output: A $t$-spanner $H$ of $G$

Initialize $H\leftarrow\emptyset$

while $\exists e\in E$ that is $t$-unspanned with respect to $H$ do:

$H\leftarrow H\cup\\{e\\}$

return $H$

It is easy to see that the resulting $H$ is indeed a $t$-spanner of $G$ since,
by construction, every edge in $G$ has a length at most $t$ path in $H$
between its endpoints. Additionally, a classic analysis shows the result is
sparse, containing at most most $n^{1+O(1/t)}$ edges [3, 2]: by construction
the graph output has girth at least $t$ (i.e. contains no cycles of length $t$
or less) and classic so-called Moore bounds state that a graph with girth at
least $t$ contains at most $n^{1+O(1/t)}$ edges. Assuming the “Erdős Girth
Conjecture” [17], this sparsity is asymptotically-optimal. Furthermore, the
greedy spanner is existentially-optimal in that its output is as sparse as
possible for any given graph family [20].

However, one downside of the greedy algorithm is its apparent sequentialness:
whether an edge is $t$-unspanned with respect to $H$ is dependent on what
edges have previously been added to $H$. Furthermore, the sparsity analysis of
the output spanner is also quite delicate in that it relies on the output
spanner having girth at most $t$ and has little to say if the girth is much
smaller than $t$.

In summary, the (sequential) greedy algorithm is one of the most well-studied
algorithms for constructing a sparse $t$-spanner but seems inherently
sequential and has a delicate sparsity analysis.

###  1.1 Our Results

In this work, we show that the classic sequential greedy algorithm, in fact,
admits significant opportunities for parallelism while (approximately)
retaining its sparsity guarantees. In particular, we show that even when many
unspanned edges are added at once the resulting graph is still sparse. To
formalize this, we generalize the above notion of an unspanned edge to a set
of edges as follows.

######  Definition 3 (Unspanned Edge Set).

Given graph $G=(V,E)$ and subgraph $H\subseteq G$, edges $\hat{E}\subseteq E$
are _$t$ -unspanned_ if each $e\in\hat{E}$ is $t$-unspanned with respect to
$H$.

Then, the parallel greedy algorithm computes a $t$-spanner $H$ by simply
repeatedly adding matchings of $t$-unspanned edges to $H$; see Algorithm 2 and
Figure 1.

Algorithm 2 Parallel Greedy Algorithm for $t$-Spanners

Input: Graph $G=(V,E)$ and $t\geq 1$

Output: A $t$-spanner $H$ of $G$

Initialize $H\leftarrow\emptyset$

while $\exists e\in E$ that is $t$-unspanned do:

Let $M\subseteq E$ be any matching in $G$ that is $t$-unspanned with respect
to $H$

$H\leftarrow H\cup M$

return $H$

(a) Input $G$.

(b) First matching.

(c) Second matching.

(d) Third matching.

Figure 1: Parallel greedy to construct a $3$-spanner. Edges not in a matching
dashed and transparent if $3$-spanned with respect to $H$. Each matching
colored and solid.

Our main result is a proof of the sparsity of the output of the parallel
greedy algorithm.

######  Theorem 1.

Parallel greedy (Algorithm 2) outputs a $t$-spanner with
$t^{3}\cdot\log^{3}n\cdot n^{1+O(1/t)}$ edges.

Even stronger, we show that parallel greedy’s output has arboricity at most
$t^{3}\cdot\log^{3}n\cdot n^{O(1/t)}$. For constant $t$, this recovers the
usual $n^{1+O(1/t)}$ bound. While we state our results for unweighted graphs,
the above can be made to work for edge-weighted graphs by a standard bucketing
trick of weights at a cost of $O(\log n)$ in the sparsity.

##### Analysis Overview.

The above result seems somewhat surprising in light of the usual analysis of
the (sequential) greedy algorithm. As mentioned above, the output of the
(sequential) greedy algorithm has low sparsity on account of its large girth.
However, a cycle on $4$ nodes demonstrates that the parallel greedy algorithm
can output a spanner with girth as small as $4$, regardless of the value of
$t$—see Figure 2. As such, an entirely different approach to analyzing the
sparsity of the output spanner is required.

(a) Input $G$.

(b) First matching.

(c) Second matching.

Figure 2: A cycle on $4$ vertices shows that parallel greedy can return
subgraphs with girth $4$ for any $t$. 2(a) gives the input graph with
$t$-unspanned edges dashed in black. 2(b) and 2(c) give the first and second
matchings added by parallel greedy in blue and red respectively.

Instead of a girth-based argument, we make use of an analysis based on length-
constrained expander decompositions, as recently introduced by [23]. Roughly
our analysis is as follows. A length-constrained expander decomposition allows
us to assume that (up to the deletion of a small number of edges), given a
matching in a graph with large minimum degree, one can find many $t$-length
paths between the matching endpoints such that no edge is used by too many
paths. On the other hand, a graph with large arboricity has a subgraph with
large minimum degree and so if the output of our algorithm has large
arboricity then we can find said non-overlapping paths for the last matching
chosen by our algorithm. Since these paths do not overlap too much, one of
them must not use any edges in the matching itself, contradicting the
$t$-unspannedness of the edges we choose. Thus, our analysis provides an
alternative approach to analyzing the sparsity of spanners output by greedy
algorithms that does not rely on delicate girth-based arguments.

##### Applications and Additional Related Work.

While we make use of the above analysis to bound the sparsity of the parallel
greedy algorithm, we believe that graphs produced by the parallel greedy
algorithm—which we call $t$-pg graphs—are a fundamental extremal object which
will find applications beyond this work. Indeed, while our approach makes use
of (the existence of) length-constrained expander decompositions, it is also
conversely useful for (algorithms for computing) length-constrained expander
decompositions. Specifically, another work [22] makes use of the sparsity of
$t$-pg graphs to argue that the union of a sequence of sparse (length-
constrained) cuts is itself a sparse (length-constrained) cut. This structural
fact, in turn, was used by [22] to give improved algorithms for computing
length-constrained expander decompositions.

Likewise, several works [6, 9, 21, 7, 8] prove lower bounds by considering
graphs that are produced by adding batches of edges (not necessarily a
matching) where no edge can complete a short cycle. For instance, this
approach has been used to prove lower bounds on fault tolerant spanners [6]
and the communication complexity of computing spanners [21].

In summary, we show that the classic greedy algorithm admits significant
opportunities for parallelism while retaining its sparsity guarantees. In the
process of showing this, we introduce a new robust way of analyzing the
density of a particular graph class which we expect to find applications
beyond spanners. The remainder of this work is dedicated to showing Theorem 1.

##  2 Notation and Conventions

We review the notation and conventions we make use of throughout this work.

##### Graphs.

Let $G=(V,E)$ be a graph and edge-length function $\l_{G}$. If unspecified
then $\l_{G}$ assigns every edge value $1$. We let $d_{G}$ denote the shortest
path metric according to $\l_{G}$ in $G$. We let $n:=|V|$ and $m:=|E|$ be the
number of vertices and edges. The _girth_ of a graph is the minimum number of
edges in a cycle. A _matching_ $M\subseteq E$ is a collection of pairwise
disjoint edges. Given edges $C$ we let $G-C:=(V,E\setminus C)$ and
$G+C:=(V,E\cup C)$. We say a subgraph is non-empty if it contains at least one
edge. We let $E_{G}(U,W):=\\{\\{u,v\\}\in E:u\in U,v\in W\\}$ and let
$\deg_{G}(v)$ give the degree of $v$ in $G$. For $U\subseteq V$, the induced
subgraph $G[U]$ on $U$ is $(V,E(U))$ where $E(U)$ is all edges in $E$ with
both endpoints in $U$. We drop $G$ subscript when it is clear from context.

##### Arboricity.

A forest cover of graph $G$ is a collection of edge-disjoint subgraphs
$F_{1},F_{2},\ldots,F_{k}$ of $G$ all of which are forests and whose union is
$G$. $k$ is the size of the forest cover and $G$ is said to have arboricity
$\alpha$ if its minimum size forest cover has size $\alpha$.

##### Flows.

A _(multicommodity) flow_ $F$ in $G$ is a function that assigns to each simple
path $P$ in $G$ a flow value $F(P)\geq 0$. We say $P$ is a _flow-path_ of $F$
if $F(P)>0$. The _congestion of $F$ on an edge $e$_ is defined to be
$\mathrm{con}_{F}(e)=\sum_{P:e\in P}F(P)$. The _congestion_ of $F$ is
$\max_{e\in E(G)}\mathrm{con}_{F}(e)$. The _length_ (a.k.a. dilation) of $F$
is the maximum length of any of its flow-paths.

##### Demands.

A _demand_ $D:V\times V\rightarrow\mathbb{R}_{\geq 0}$ assigns a non-negative
value $D(v,w)\geq 0$ to each ordered pair of vertices in $V$. The load of
demand $D$ is defined as

$\text{load}(D):=\max_{v}\left(\max\left(\sum_{u}D(u,v),\sum_{u}D(v,u)\right)\right).$

A demand $D$ is _unit_ if we have $\text{load}(D)\leq\deg(v)$ for every $v\in
V$. The size of a demand is written as $|D|$ and is defined as
$\sum_{v,w}D(v,w)$. A demand $D$ is called _$h$ -length_ constrained (or
simply _$h$ -length_) in $G$ if it assigns positive values only to pairs that
are within distance at most $h$ in $G$. Given a flow $F$, the _demand routed
by $F$_ is denoted by $D_{F}$ where, for each $u,v\in V$,
$D_{F}(u,v)=\sum_{P\text{ is a path from $u$ to $v$}}F(P)$ is the value of the
flow from $u$ to $v$.

##### Routing Demands and Matchings with Flows.

We say that a _demand $D$ is routable in $G$ with congestion $\eta$ and
dilation $h$_ iff there exists a flow $F$ in $G$ with congestion $\eta$ and
dilation $h$ where $D_{F}=D$. We say that a matching $M\subseteq E$ is
$\delta$-routable with congestion $\eta$ and dilation $h$ if the demand
$D_{M}(u,v)=\delta$ iff $\\{u,v\\}\in M$ and $0$ otherwise is routable with
congestion $\eta$ and dilation $h$; here we imagine that each $e\in M$ has a
canonical $u$ and $v$ so that $\text{load}(D_{M})\leq\delta$.

##  3 High Degree Subgraphs with Routable Matchings

Towards bounding the arboricity of the output of our parallel greedy
algorithm, in this section we show that any graph of high minimum degree has a
non-empty subgraph of essentially the same minimum degree where any matching
can be routed with low dilation and congestion. Specifically, we show the
following where $\Theta_{\ref{thm: linked ED}}$ is a fixed universal constant
hidden in Theorem 3; later stated.

######  Lemma 1.

There exist universal constants $\Theta_{\ref{thm:flow character}}$,
$\Theta_{\ref{thm: linked ED}}$ such that for every $t\geq 2$ if we let

$\framebox{$\phi:=1/(2t\cdot n^{\Theta_{\ref{thm: linked ED}}/t}\cdot\log
n)$}\qquad and\qquad\framebox{$\delta:=4\Theta_{\ref{thm:flow character}}\cdot
t\log n/\phi^{2}$}$

then every $n$-vertex graph $H$ of minimum degree $\delta$, has a non-empty
subgraph $H^{\prime}\subseteq H$, such that

  1. 1.

Minimum Degree: $H^{\prime}$ has minimum degree at least
$\delta^{\prime}:=\frac{\phi}{2t}\cdot\delta$; and

  2. 2.

Routings: Any matching $M\subseteq H^{\prime}$ is $\delta^{\prime}$-routable
in $H^{\prime}$ with dilation $t$ and congestion $\delta^{\prime}/2$.

Observe that $\delta^{\prime}$-routing a matching with dilation $1$ and
congestion $\delta^{\prime}$ is trivial; notably the above improves this to
congestion $o(\delta^{\prime})$. The rest of this section proves Lemma 1 with
length-constrained expander decompositions.

###  3.1 Preliminary: Length-Constrained Expander Decompositions

Our proof of Lemma 1 makes use of length-constrained expander decompositions
and so we begin by providing background on length-constrained expander
decompositions, mostly from [23]. In short, a length-constrained expander
decomposition is a small number of edge length increases so that every length-
constrained unit demand in the resulting graph can be routed with low
congestion and dilation.

####  3.1.1 Length-Constrained Cuts (a.k.a. Moving Cuts)

We begin by giving formal definitions of length-constrained cuts which will
allow us to define length-constrained expanders and length-constrained
expander decompositions.

The following is the length-constrained analogue of a cut.

######  Definition 4 (Length-Constrained Cut (a.k.a. Moving Cut) [24]).

An $h$-length cut (a.k.a. $h$-length moving cut) of graph $G=(V,E)$ is a
function $C:E\mapsto\\{0,\frac{1}{h},\frac{2}{h},\dots,1\\}$. The _size_ of
$C$ is $|C|:=\sum_{e}C(e)$. Any length-constrained cut with support in
$\\{0,1\\}$ is called pure.

The following is the result of applying a length-constrained cut in a graph.

######  Definition 5 ($G-C$).

For graph $G=(V,E)$ with edge length function $\l_{G}$ and length-constrained
cut $C$, we let $G-C$ be $G$ with the edge-length function which assigns $e\in
E$ value $\l_{G}(e)+h\cdot C(e)$. If $C$ is a pure cut then $G-C$ is $G$ with
all edges in the support of $C$ deleted.

The following gives the length-constrained analogue of separating a demand.

######  Definition 6 ($h$-Length Separated Demand).

For any demand $D$ and any $h$-length cut $C$, we define the amount of
$h$-length separated demand as

$\operatorname{sep}_{h}(C,D)=\sum_{u,v:d_{G-C}(u,v)>h}D(u,v).$

Using demand separation, we can define cut sparsity in the length-constrained
setting.

######  Definition 7 ($h$-Length Sparsity of a Cut $C$ for Demand $D$).

For any demand $D$ and any $h$-length cut $C$ with
$\operatorname{sep}_{h}(C,D)>0$, the $h$-length sparsity of $C$ with respect
to $D$ is

$\operatorname{spars}_{h}(C,D)=\frac{|C|}{\operatorname{sep}_{h}(C,D)}.$

Likewise, we can define the overall sparsity of a length-constrained cut as
follows.

######  Definition 8 ($(h,s)$-Length Sparsity of a Cut).

The $(h,s)$-length sparsity of $hs$-length cut $C$ is:

$\operatorname{spars}_{(h,s)}(C)=\min_{\text{h-length unit demand}\
D}\operatorname{spars}_{s\cdot h}(C,D).$

####  3.1.2 Length-Constrained Expanders

We now move on to formally defining length-constrained expanders. Informally,
they are graphs with no sparse length-constrained cuts.

######  Definition 9 ($(h,s)$-Length $\phi$-Expanders).

A graph $G$ is an $(h,s)$-length $\phi$-expander if every $hs$-length cut has
$(h,s)$-length sparsity at least $\phi$.

We now summarize the crucial properties of length-constrained expanders,
namely the fact that they admit low congestion and dilation routings (see
Lemma 3.16 of [23]).

######  Theorem 2 (Routing Characterization of Length-Constrained Expanders,
[23]).

Given graph $G$, for any $h\geq 1$, $\phi<1$, and $s\geq 1$, there exists a
universal constant $\Theta_{\ref{thm:flow character}}$:

  * •

Length-Constrained Expanders Have Good Routings: If $G$ is an $(h,s)$-length
$\phi$-expander, then every $h$-length unit demand can be routed in $G$ with
congestion at most $\Theta_{\ref{thm:flow character}}\cdot\log n/\phi$ and
dilation at most $s\cdot h$.

  * •

Not Length-Constrained Expanders Have an Unroutable Demand: If $G$ is not an
$(h,s)$-length $\phi$-expander, then some $h$-length unit demand cannot be
routed in $G$ with congestion at most $1/2\phi$ and dilation at most
$\frac{s}{2}\cdot h$.

####  3.1.3 Length-Constrained Expander Decompositions

Having defined length-constrained expanders, we can now define length-
constrained expander decompositions. Informally, these are length-constrained
cuts whose application renders the graph a length-constrained expander.

More specifically, we will make use of a strengthened version of length-
constrained expander decompositions called “linked” length-constrained
expander decompositions. Informally, this is a length-constrained expander
decomposition which renders $G$ length-constrained expanding even after adding
many self-loops. This is a strengthened version because adding self-loops only
makes it harder for a graph to be a length-constrained expander.

The following definition gives the self-loops we will add for a length-
constrained expander decomposition $C$.

######  Definition 10 (Self-Loop Set $L^{\ell}_{C}$).

Let $C$ be an $h$-length cut of a graph $G=(V,E)$ and let $\ell$ be a positive
integer divisible by $h$. For any vertex $v$, define $C(v)=\sum_{e\ni v}C(e)$.
The self-loop set $L^{\ell}_{C}$ consists of $C(v)\cdot\ell$ self-loops at
$v$. We let $G+L^{\ell}_{C}:=(V,E\cup L^{\ell}_{C})$.

Using the above self-loops, we can now define linked length-constrained
expander decompositions.

######  Definition 11 (Linked Length-Constrained Expander Decomposition).

Let $G$ be a graph. An $\ell$-linked $(h,s)$-length $\phi$-expander
decomposition with cut slack $\kappa$ is an $hs$-length cut $C$ such that
$|C|\leq\kappa\cdot\phi m$ and $G+L^{\ell}_{C}-C$ is an $(h,s)$-length
$\phi$-expander.

Prior work of [23] demonstrated that for each $\phi$, a length-constrained
expander decomposition always exist with length slack $s=\Omega(n)$, cut slack
$\kappa=O(\log n)$ and linkedness $\ell\geq\Omega(1/\phi\cdot\log n)$.

###  3.2 Existence of Length-Constrained Expander Decompositions

In this work we will use the existence of pure length-constrained expanders
which trade-off between $s$ and $\kappa$. Namely, we show the following
theorem; our proof essentially follows that of [23] but accounts for the
pureness of our decompositions (paying an extra $h$ in $\kappa$) and uses a
more general form of the “exponential demand”.

######  Theorem 3 (Length-Constrained Expander Decompositions).

There exists a constant $\Theta_{\ref{thm: linked ED}}$ such that given graph
$G=(V,E)$ with edge lengths, $h\geq 1$, $s\geq 100$, $\phi\geq 0$ and any
$\ell\leq 1/(100\phi\log n)$, there exists a pure $\ell$-linked $(h,s)$-length
$\phi$-expander decomposition with cut slack $hs\cdot n^{\Theta_{\ref{thm:
linked ED}}/s}\cdot\log n$.

###### Proof.

We denote by $d(\cdot,\cdot)$ the shortest-path distance between edges in $G$.
That is, for a pair $e,e^{\prime}\in E(G)$, $d(e,e^{\prime})$ is the smallest
total length of any path starting with $e$ and ending with $e^{\prime}$.

We now define a demand $D$ on $G$ as follows. For a pair $e,e^{\prime}$ of
edges in $G$, we set $w(e,e^{\prime})=n^{-d(e,e^{\prime})/(sh/2)}$ if
$d(e,e^{\prime})\leq sh/2$, otherwise we set $w(e,e^{\prime})=0$. Denote
$w(e)=\sum_{e^{\prime}}w(e,e^{\prime})$, and define
$D(e,e^{\prime})=w(e,e^{\prime})/w(e)$, so for each $e$,
$\sum_{e^{\prime}}D(e,e^{\prime})=1$. Intuitively, we can think of $D$ as a
demand that sends, for each pair $e,e^{\prime}$, $D(e,e^{\prime})$ units of
flow from $e$ to $e^{\prime}$. Formally, we define the demand on vertices as
follows. For every pair $v,v^{\prime}$ of vertices in $G$, we send
$D(v,v^{\prime})=\sum_{e\sim v,e^{\prime}\sim v^{\prime}}D(e,e^{\prime})$
units of flow from $v$ to $v^{\prime}$. As
$\sum_{e^{\prime}}D(e,e^{\prime})=1$ holds for all $e$, we get that the demand
$D$ we defined on pairs of vertices is unit. We prove the following two
claims.

######  Claim 1.

For every pair $e,e^{\prime}$ with $d(e,e^{\prime})\leq h$,
$\sum_{e^{\prime\prime}}\min\left\\{D(e,e^{\prime\prime}),D(e^{\prime},e^{\prime\prime})\right\\}\geq
n^{-4/s}$.

###### Proof.

Observe that, for every $e^{\prime\prime}$,

$w(e^{\prime},e^{\prime\prime})=n^{-\frac{d(e^{\prime},e^{\prime\prime})}{(sh/2)}}\geq
n^{-\frac{d(e,e^{\prime})+d(e,e^{\prime\prime})}{(sh/2)}}\geq
n^{-\frac{h}{(sh/2)}}\cdot
n^{-\frac{d(e,e^{\prime\prime})}{(sh/2)}}=n^{-2/s}\cdot
w(e,e^{\prime\prime}),$

and as a corollary,

$w(e^{\prime})=\sum_{e^{\prime\prime}}w(e^{\prime},e^{\prime\prime})=\sum_{e^{\prime\prime}}n^{-\frac{d(e^{\prime},e^{\prime\prime})}{(sh/2)}}\geq\sum_{e^{\prime\prime}}n^{-2/s}\cdot
w(e,e^{\prime\prime})=n^{-2/s}\cdot w(e).$

Therefore,

$\begin{split}\sum_{e^{\prime\prime}}\min\left\\{D(e,e^{\prime\prime}),D(e^{\prime},e^{\prime\prime})\right\\}&\geq\sum_{e^{\prime\prime}}\min\left\\{\frac{w(e,e^{\prime\prime})}{w(e)},\frac{w(e^{\prime},e^{\prime\prime})}{w(e^{\prime})}\right\\}\\\
&\geq\sum_{e^{\prime\prime}}\frac{n^{-2/s}\cdot
w(e,e^{\prime\prime})}{n^{2/s}\cdot w(e)}\\\ &\geq n^{-4/s}.\end{split}$

∎

######  Claim 2.

Let $C$ be any moving cut with $\operatorname{spars}_{(h,s)}(C)\leq\phi$. Then
$\operatorname{spars}_{h,s/2}(C,D)\leq 2\phi n^{4/s}$.

###### Proof.

Let $D^{*}$ be a unit $h$-hop demand with
$\operatorname{spars}_{(h,s)}(C,D^{*})\leq\phi$. As $D^{*}$ is a unit demand,
we first distributed the demand on each vertex to its incident edges, such
that each edge sends and receives at most $1$ unit of flow. Consider the
resulting demand $D^{**}$ on edges. Note that, by concatenating a demand of
$D^{**}(e,e^{\prime})\cdot\min\left\\{D(e,e^{\prime\prime}),D(e^{\prime},e^{\prime\prime})\right\\}$
from $e$ to every $e^{\prime\prime}$ and a demand from $e^{\prime\prime}$ to
$e^{\prime}$ with the same amount, where we essentially applied the demand $D$
twice (where the second time we use it in the opposite direction), we obtain a
demand that sends at least $D^{**}(e,e^{\prime})\cdot n^{-4/s}$ units of flow
from $e$to $e^{\prime}$, for every pair $e,e^{\prime}$. If $e$ and
$e^{\prime}$ are at distance at least $sh$ in $G-C$ then either the pair
$e,e^{\prime\prime}$ or the pair $e^{\prime\prime},e$ must be at distance at
least $sh/2$. Therefore,
$\operatorname{sep}_{hs/2}(C,D)\geq(n^{-4/s}/2)\cdot\operatorname{sep}_{hs}(C,D^{*})$,
and so $\operatorname{spars}_{(h,s/2)}(C,D)\leq
2n^{-4/s}\cdot\operatorname{spars}_{(h,s)}(C,D^{*})\leq 2\phi n^{4/s}$. ∎

We now provide the proof of Theorem 3 by a simple algorithm. While there
exists a moving cut $C$ in $G$ that is $(h,s)$-hop $\phi$-sparse, we let
$\bar{C}$ be the pure cut corresponding to $C$ (that is, $\bar{C}$ contains
all edges with non-zero values in $C$, so $|\bar{C}|\leq hs\cdot|C|$), update
$G\leftarrow G-\bar{C}+L^{\ell}_{\bar{C}}$ and continue. It is easy to verify
that our algorithm ends with $G$ being an $\ell$-linked $(h,s)$-hop
$\phi$-expander.

It suffices to count the total number of deleted edges, for which we define a
potential function as follows. For each edge (including self-loop) in $G$, we
define its potential to be $\ln(w(e))\cdot 4hsn^{4/s}$. For every unit of
moving cut that we applied to $G$, we define its potential to be $1/\phi$.
Initially, the total potential is at most $|E(G)|\cdot\log|E(G)|\cdot 4hs\cdot
n^{4/s}$ (each edge has potential at most $\log|E(G)|\cdot 4hs\cdot n^{4/s})$
and there is no moving cut applied. We will show that, after each iteration
(where a cut is applied to $G$ and corresponding self-loops are added), the
potential never increases. Note that this implies that the total number of
deleted edges is at most $\phi\cdot|E(G)|\cdot\log|E(G)|\cdot 4hs\cdot
n^{4/s}$, completing the proof of Theorem 3 (as $|E(G)|\leq n^{2}$).

According to the algorithm, in an iteration where a sparse cut $C$ is found,
we apply $\bar{C}$ to $G$ and add self-loops, which increases the potential by
at most

$|C|\cdot hs/\phi+|C|\cdot hs\cdot\ell\log n\leq 2\cdot|C|\cdot hs/\phi,$

as $\ell\leq 1/(100\phi\log n)$. On the other hand, the potential decrease is
at least

$4n^{4/s}\cdot hs\cdot\sum_{e\in E(G)}\ln(w(e))-\ln(w^{\prime}(e))\geq
4n^{4/s}\cdot hs\cdot\sum_{e\in E(G)}\frac{w(e)-w^{\prime}(e)}{w(e)},$

where $w^{\prime}(e)$ represents the weight of $e$ in the updated graph $G$.
From 2, we know that the $(h,s/2)$-hop sparsity of $C$ for $D$ is at most
$2\phi n^{4/s}$. This means that $\operatorname{sep}_{sh/2}(C,D)\geq|C|/(2\phi
n^{4/s})$. On the other hand, by definition of $D$, the right-hand-side of the
above inequality is at least the amount of demand that is $sh/2$-separated by
$C$ (as those demand will have weight $w^{\prime}(e,e^{\prime})=0$ according
to our definition), and so is at least $|C|/(2\phi n^{4/s})$. Altogether, we
get that the potential decrease is at least

$4n^{4/s}\cdot hs\cdot|C|/(2\phi n^{4/s})\geq 2\cdot|C|\cdot hs/\phi,$

which is an upper bound of the potential increase. This completes the proof
that the potential never increases. ∎

###  3.3 High Degree Routable Matching Subgraphs (Lemma 1 Proof)

We conclude this section with our proof of Lemma 1.

See 1

###### Proof.

The basic idea of the proof is as follows. We first take a linked length-
constrained expander decomposition. Then, the result of applying this length-
constrained expander decomposition must have high minimum degree because if
any vertex $v$ has its degree drop too low we can find a sparse length-
constrained cut (namely the singleton cut separating that $v$). Likewise,
matchings are routable with low dilation and congestion because the result of
applying our length-constrained expander decomposition is a length-constrained
expander.

We begin by more formally describing our length-constrained expander
decomposition. Specifically, we apply Theorem 3 to graph $H$ with parameters
$h=1$, $s=t$ and $\ell=1/(100\phi\log n)$. We let $C$ be the resulting pure
cut which is a $1/(100\phi\log n)$-linked $(h,s)$-length $\phi$-expander
decomposition for $H$ with cut slack $t\cdot n^{\Theta_{\ref{thm: linked
ED}}/t}\cdot\log n$.

We first define $H^{\prime}$. Observe that by our choice of $\phi$ we have

$\displaystyle|C|$ $\displaystyle\leq t\cdot n^{\Theta_{\ref{thm: linked
ED}}/t}\cdot\log n\cdot\phi\cdot|E(H)|$ $\displaystyle\leq\frac{|E(H)|}{2}$

and therefore $H-C$ contains at least one edge. We let $H^{\prime}$ be an
arbitrary connected component of $H-C$ with at least one edge. It remains to
show that $H^{\prime}$ satisfies the properties required in Lemma 1.

We first show that the minimum degree in $H^{\prime}$ is at least
$\delta^{\prime}$. Assume for the sake of contradiction that there is a vertex
$v$ in $H^{\prime}$ such that $\deg_{H^{\prime}}(v)<\delta^{\prime}$. Since
$H^{\prime}$ is a connected graph with at least two vertices, $v$ has at least
one neighbor in $H^{\prime}$; let $u$ be an arbitrary such neighbor. By our
choice of $\phi$ and $l$, we have that

$\displaystyle l=1/(100\phi\log n)=t\cdot n^{\Theta_{\ref{thm: linked
ED}}/t}/50=\omega(1)\geq 2$ (1)

and

$\displaystyle\delta^{\prime}=\frac{\phi}{2t}\cdot\delta=\frac{1}{4t^{2}\cdot
n^{\Theta_{\ref{thm: linked ED}}/t}\cdot\log
n}\cdot\delta\leq\frac{\delta}{2}.$ (2)

Thus, from the definition of the set $L_{C}^{\ell}$ and our choice of
$\delta^{\prime}$ and $\phi$ and applying Equations 1 and 2, the number of
self loops at $v$ in $H-C+L_{C}^{\ell}$ is at least

$\displaystyle(\delta-\delta^{\prime})\cdot l\geq\delta.$

Likewise, the degree of $u$ in $H-C+L_{C}^{\ell}$ is at least $\delta$ since
in $H$ it has degree at least $\delta$, and if the cut $C$ assigns non-zero
values to $d$ of its incident edges, then $d\ell>d$ self-loops will be added
to $u$.

Next, consider the demand $D_{0}$ which gives value $\delta$ to $(u,v)$ and
$0$ to all other pairs of vertices. Since both $u$ and $v$ have degree at
least $\delta$ in $H-C+L_{C}^{\ell}$, it follows that $D_{0}$ is unit in
$H-C+L_{C}^{\ell}$. Likewise, since $u$ and $v$ are adjacent in $H^{\prime}$,
$D_{0}$ is a $1$-length demand in $H-C+L_{C}^{\ell}$.

Let $C_{0}$ be the length-constrained cut that assigns value $t$ to all edges
in
$E_{H^{\prime}}(\left\\{v\right\\},V(H^{\prime})\setminus\left\\{v\right\\})$
and value $0$ to all other edges. Since $v$ has degree at most
$\delta^{\prime}$ in $H^{\prime}$ we have

$\displaystyle|C_{0}|\leq t\cdot\delta^{\prime}.$ (3)

However, $C_{0}$ $t$-separates $D_{0}$ in $H-C+L_{C}^{\ell}$ and since $D_{0}$
is a unit $1$-length demand and $H-C+L_{C}^{\ell}$ is a $(1,t)$-length
$\phi$-expander it follows that

$\displaystyle|C_{0}|\geq\phi\cdot|D_{0}|=\phi\cdot\delta.$ (4)

Combining Equations 3 and 4 we get

$\displaystyle\phi\cdot\delta\leq t\cdot\delta^{\prime}$

which contradicts the definition of $\delta^{\prime}$ as
$\frac{\phi}{2t}\cdot\delta$.

It remains to show that any matching in $H^{\prime}$ is
$\delta^{\prime}$-routable with dilation $t$ and congestion at most
$\delta^{\prime}/2$. Consider matching $M\subseteq H^{\prime}$ and let $D_{M}$
be the demand which assigns $(u,v)$ value $\delta^{\prime}$ for each
$\\{u,v\\}\in M$ (for a canonical ordering of the vertices). $D_{M}$ is
$1$-length by construction and unit in $H^{\prime}$ since every vertex in
$H^{\prime}$ has degree at least $\delta^{\prime}$. Furthermore, $H^{\prime}$
is a $(1,t)$-length $\phi$-expander since $H-C+L_{C}^{\ell}$ is and so $D_{M}$
can be routed with dilation $t$ and congestion

$\displaystyle\Theta_{\ref{thm:flow character}}\cdot\log
n/\phi\leq\delta^{\prime}/2$

in $H^{\prime}$. ∎

##  4 Bounding the Arboricity of Parallel Greedy Graphs

Having shown how to route in high minimum degree graphs in the previous
section, in this section we bound the arboricity of any graph constructed in
the manner of the parallel greedy algorithm. We abstract out such graphs with
the notion of a parallel greedy graph.

######  Definition 12 ($t$-pg Graphs).

Let $V$ be a set of vertices. We say that a sequence of edge sets
$(E_{1},\ldots,E_{k})$ on $V$ is $t$-pg for some integer $t\geq 2$, iff for
each $i\in[k]$,

  * •

$E_{i}$ is a matching on $V$; and

  * •

$d_{G_{i-1}}(u,v)>t$ for each $(u,v)\in E_{i}$ where $G_{i-1}$ the graph on
$V$ with edges $\bigcup_{1\leq j\leq i-1}E_{j}$.

We say that a graph $G=(V,E)$ is $t$-pg iff its edge set $E$ is the union of
some $t$-pg sequence on $V$.

The following summarizes our bound on the arboricity of $t$-pg graphs.

######  Theorem 4.

Every $t$-pg graph on $n$ vertices has arboricity $t^{3}\cdot\log^{3}n\cdot
n^{O(1/t)}$.

The remainder of this section is dedicated to a proof of Theorem 4. In
particular, we will observe that if our parallel greedy graph has high
arboricity then it has a high minimum degree subgraph and this subgraph admits
low congestion and dilation routings (by Lemma 1). We will then use these
routings to contradict the parallel greediness of the input graph.

###  4.1 Preliminary: Minimum-Degree Subgraphs from Arboricity

We begin by noting a known fact about high minimum degree subgraphs of high
arboricity graphs.

######  Lemma 2.

Let $G=(V,E)$ be a graph with arboricity $\alpha$. Then, $G$ has a non-empty
induced subgraph with minimum degree at least $\alpha/2$.

The rest of this section is dedicated to showing this folklore fact using some
standard arguments.

To show Lemma 2, we will make use of a famous result of Nash-Williams
characterizing graph arboricity in terms of graph density as well as two
simple helper lemmas.

######  Theorem 5 ([26, 27, 14]).

Graph $G=(V,E)$ has arboricity at most $\alpha$ iff for every $U\subseteq V$
we have

$\displaystyle|E(U)|\leq\alpha\cdot(|U|-1).$

Likewise we make use of the following two simple helper lemmas.

######  Lemma 3.

Let $G=(V,E)$ be a connected graph with arboricity $\alpha$. Then
$|E|+1\geq|V|-1+\alpha$.

###### Proof.

Let $F_{1},F_{2},\ldots,F_{\alpha}$ be the minimum size forest decomposition
of $G$. We may assume that $F_{1}$ is a spanning tree of $G$ since if it is
not we can always move edges from $F_{i}$ for $i\geq 2$ to $F_{1}$ to make it
a spanning tree. Furthermore, we may assume that each $F_{i}$ contains at
least one edge (otherwise we would have violated the definition of
arboricity). It follows that $F_{1}$ contains $|V|-1$ unique edges and $F_{i}$
for $i\geq 2$ contains at least one unique edge, giving the inequality. ∎

######  Lemma 4.

Let $G=(V,E)$ be a graph with average degree
$\rho:=\frac{\sum_{u}\deg_{G}(u)}{|V|}$. Then there is a non-empty $U\subseteq
V$ such that $G[U]$ has minimum degree at least $\rho/2$.

###### Proof.

Our proof is by the following construction: initialize $U$ to $V$; while there
exists a vertex $u\in U$ such that $\deg_{G[U]}(u)<\rho/2$ remove $u$ from
$U$. By construction the minimum degree of $G[U]$ is at least $\rho/2$.

To see that $U$ is non-empty, let

$\displaystyle\rho_{U}:=\frac{\sum_{u\in U}\deg_{G[U]}(u)}{|U|}$

be the average degree of $U$. It suffices to show that our construction always
satisfies $\rho_{U}>0$ since if $U$ is empty at the end of our construction
then at some point the numerator of $\rho_{U}$ would be $0$ and the
denominator would be $1$ (namely, when $|U|=1$). This follows since initially
$\rho_{U}$ has value $\rho$ and each time we remove a vertex from $u$ we
decrease the numerator of $\rho_{U}$ by strictly less than $\rho$ and the
denominator by $1$. ∎

Using the above theorem of Nash-Williams and our two helper lemmas, we
conclude with a proof of Lemma 2. See 2

###### Proof.

By Theorem 5 there is a non-empty $U\subseteq V$ such that

$\displaystyle|E(U)|\geq(\alpha-1)\cdot(|U|-1)+1$ (5)

since other we could decrease $\alpha$ by $1$ and still satisfy the inequality
in Theorem 5, contradicting Theorem 5. We can assume without loss of
generality that $U$ is connected. Applying Lemma 3 and the fact that $G[U]$
has arboricity at least $\alpha$ we have

$\displaystyle|E(U)|+1\geq|U|-1+\alpha$ (6)

Thus, combining Equations 5 and 6 we have

$\displaystyle 2|E(U)|\geq\alpha\cdot|U|$

It follows that the average degree of a vertex in $G[U]$ is

$\displaystyle\frac{\sum_{u\in
U}\deg_{G[U]}(u)}{|U|}=\frac{2|E(U)|}{|U|}\geq\alpha.$

and so by Lemma 4 we know that $G[U]$ and therefore $G$ contains a subgraph of
minimum degree at least $\alpha/2$. ∎

###  4.2 Arboricity of Parallel Greedy Graphs (Theorem 4 Proof)

In this section, we provide the proof of Theorem 4. We make use of Lemma 1 and
Lemma 2 from previous sections. We also make use of the following simple
helper lemma.

######  Lemma 5.

Every subgraph of a $t$-pg graph is also a $t$-pg graph.

###### Proof.

Let $G$ be a $t$-pg graph and let $H$ be a subgraph of $G$. Let
$(E_{1},\ldots,E_{k})$ be the $t$-pg sequence that generates $G$. For each
$i\in[k]$, let $E^{\prime}_{i}$ be the subset of $E_{i}$ that contains all
edges lying in $H$. Clearly, $E^{\prime}_{i}$ is a matching in $H$, and if we
denote by $H_{i-1}$ the graph induced by edges in $\bigcup_{1\leq j\leq
i-1}E^{\prime}_{j}$, then for every edge $(u,v)\in E^{\prime}_{i}$ we have

$\displaystyle d_{H_{i-1}}(u,v)>t.$

This follows because otherwise we have

$\displaystyle d_{G_{i-1}}(u,v)\leq d_{H_{i-1}}(u,v)\leq t$

and since $H_{i-1}$ is a subgraph of $G_{i-1}$ and $(u,v)$ is also an edge in
$E_{i}$, this leads to a contradiction to the assumption that
$(E_{1},\ldots,E_{k})$ is a $t$-pg sequence. ∎

We conclude with our proof of Theorem 4, illustrated in Figure 3.

(a) Input $t$-pg graph $G$.

(b) Subgraph $H\subseteq G$.

(c) Demand routed.

(d) $t$-length path.

Figure 3: Our proof of the bound on the arboricity of a $t$-pg graph. 3(a)
gives our input $t$-pg graph $G$ where the last matching $M$ is in green. 3(b)
gives the subgraph $H\subseteq G$ of large minimum degree implied by Lemma 2.
3(c) gives the demand that Lemma 1 routes with congestion $\delta^{\prime}/2$
and 3(d) gives in blue the $t$-length path between endpoints of an edge in $M$
that does not contain an edge in $M$. The existence of this path is implied by
the flow of Lemma 1 as applied to $H$ and this path contradicts the fact that
$G$ is $t$-pg assuming $t\geq 10$.

See 4

###### Proof.

Throughout this proof we use the following parameters:

$\phi=1/(2\cdot t\cdot n^{\Theta_{\ref{thm: linked ED}}/t}\cdot\log
n)\quad\quad\text{and}\quad\quad\delta=4\Theta_{\ref{thm:flow character}}\cdot
t\log n/\phi^{2}=t^{3}\cdot\log^{3}n\cdot n^{O(1/t)}$

where $\Theta_{\ref{thm: linked ED}}$ is the constant stated in Theorem 3 and
$\Theta_{\ref{thm:flow character}}$ is the constant stated in Theorem 2.

Let $G$ be any $t$-pg graph. Assume for contradiction that $G$ has arboricity
greater than $2\delta$. It follows by Lemma 2 that $G$ has a non-empty
(induced) subgraph $H$ of minimum degree at least $\delta$.

We now use Lemma 1 to complete the proof. We apply Lemma 1 to $H$, $\phi$ and
$t$. Let $H^{\prime}$ be the subgraph we obtain, so $H^{\prime}$ is a subgraph
of $H$ and a subgraph of $G$, and therefore also a $t$-pg graph (by Lemma 5).
Let $(E^{\prime}_{1},\ldots,E^{\prime}_{k})$ be a $t$-pg sequence that
generates $H^{\prime}$. Denote $M=E^{\prime}_{k}$ as the last set in this
sequence.

From Lemma 1, there exists a flow $F$ that sends
$\delta^{\prime}=\frac{\phi}{2t}\cdot\delta$ units of flow from $u$ to $v$ in
$H^{\prime}$ for each edge $\\{u,v\\}\in M$ with congestion
$\delta^{\prime}/2$ and dilation $t$. Thus, the total amount of flow sent by
$F$ from sources to sinks is $|M|\cdot\delta^{\prime}$. On the other hand,
each edge in $H^{\prime}$ carries at most $\delta^{\prime}/2$ units of flow
and so all edges of $M$ carry at most
$|M|\cdot(\delta^{\prime}/2)<|M|\cdot\delta^{\prime}$ units of flow.

Thus, some flow must be sent along a path that does not contain edges of $M$.
Let $\\{u,v\\}$ be the endpoints of such a path. As the flow only uses paths
of length at most $t$, this implies that $d_{H^{\prime}\setminus M}(u,v)\leq
t$, and it follows that $d_{H^{\prime}\setminus M}(u,v)\leq t$, a
contradiction to the fact that $H^{\prime}$ is a $t$-pg graph. ∎

##  5 Sparse Spanner from Parallel Greedy (Theorem 1 Proof)

We conclude with our proof that the parallel greedy algorithm produces a
sparse $t$-spanner. See 1

###### Proof.

The argument that the output graph $H$ is a $t$-spanner is identical to the
usual analysis of the greedy algorithm; in particular, if $G$ has no
$t$-unspanned edges with respect to $H$ then $H$ is a $t$-spanner. This
follows since in such an $H$, every edge $\\{u,v\\}\in G$ is either in $H$ or
$d_{H}(u,v)\leq t$. Thus, for two arbitrary vertices $u$ and $v$ with shortest
path $P=(u=v_{0},v_{1},v_{2},\ldots,v_{k}=v)$ in $G$ we have
$d_{H}(v_{i-1},v_{i})\leq t$ for each $i\in[k]$ and so

$\displaystyle d_{H}(u,v)\leq\sum_{i\in[k]}d_{H}(v_{i-1},v_{i})\leq
t\cdot|P|=t\cdot d_{G}(u,v).$

Likewise, by construction the output of the parallel greedy algorithm is a
$t$-pg graph. Thus, by Theorem 4 it has arboricity at most
$t^{3}\cdot\log^{3}n\cdot n^{O(1/t)}$ and so contains at most
$t^{3}\cdot\log^{3}n\cdot n^{1+O(1/t)}$ edges. ∎

##  6 Conclusion and Future Directions

In this work we showed that the classic greedy algorithm for constructing
$t$-spanners produces sparse $t$-spanners even when many edges from a matching
are added in parallel. Using a simple application of length-constrained
expander decompositions, we demonstrated that this process results in a graph
with at most $t^{3}\cdot\log^{3}n\cdot n^{1+O(1/t)}$ edges.

The most obvious future direction is to tightly characterize the density of
the spanners produced by this algorithm. In contrast, to the classic
sequential greedy algorithm, simple examples (e.g. the $n$-dimensional
hypercube) demonstrate that the $t$-spanners produced by the parallel greedy
algorithm contain at least $\Omega(n\cdot\log n)$-many edges. As such, an
exciting future direction is to determine whether or not this simple lower
bounds can be matched on the upper bounds side. Furthermore, our work is a
simple application of length-constrained expander decompositions. Work in
algorithms work has only recently begun to fully develop applications of these
decompositions and so we leave further applications as an exciting future
direction. Likewise, we believe $t$-pg are a fundamental graph class and leave
further applications of their sparsity as a future direction.

## Acknowledgements

We would like to thank Greg Bodwin for helpful comments and references.

Haeupler and Hershkowitz supported in part by NSF grants CCF-1527110,
CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF1750808, a Sloan
Research Fellowship, funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation program (ERC grant
agreement 949272) and the Swiss National Foundation (project grant
200021_184735). Hershkowitz also funded by the SNSF, Swiss National Science
Foundation grant 200021_184622. Tan supported by a grant to DIMACS from the
Simons Foundation (820931).

## References

  * ABP [90] Baruch Awerbuch, Alan Baratz, and David Peleg.  Cost-sensitive analysis of communication protocols.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 177–187, 1990.
  * ABS+ [20] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence.  Graph spanners: A tutorial review.  Computer Science Review, 37:100253, 2020.
  * ADD+ [93] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.
  * Awe [85] Baruch Awerbuch.  Communication-time trade-offs in network synchronization.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 272–276, 1985.
  * Awe [92] Baruch Awerbuch.  Efficient broadcast and light-weighted spanners.  manuscript, 1992.
  * BDPW [18] Greg Bodwin, Michael Dinitz, Merav Parter, and Virginia Vassilevska Williams.  Optimal vertex fault tolerant spanners (for fixed stretch).  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1884–1900. SIAM, 2018.
  * BDR [22] Greg Bodwin, Michael Dinitz, and Caleb Robelle.  Partially optimal edge fault-tolerant spanners.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3272–3286. SIAM, 2022.
  * BHT [22] Greg Bodwin, Gary Hoppenworth, and Ohad Trabelsi.  Bridge girth: A unifying notion in network design.  arXiv preprint arXiv:2212.11944, 2022.
  * BJ [17] Boris Bukh and Zilin Jiang.  A bound on the number of edges in graphs without an even cycle.  Combinatorics, Probability and Computing, 26(1):1–15, 2017.
  * BKR+ [02] Rebecca Braynard, Dejan Kostic, Adolfo Rodriguez, Jeffrey Chase, and Amin Vahdat.  Opus: an overlay peer utility service.  In 2002 IEEE Open Architectures and Network Programming Proceedings. OPENARCH 2002 (Cat. No. 02EX571), pages 167–178. IEEE, 2002.
  * BSDS [04] Yehuda Ben-Shimol, Amit Dvir, and Michael Segal.  Splast: a novel approach for multicasting in mobile wireless ad hoc networks.  In 2004 IEEE 15th International Symposium on Personal, Indoor and Mobile Radio Communications (IEEE Cat. No. 04TH8754), volume 2, pages 1011–1015. IEEE, 2004.
  * CKR+ [91] Jason Cong, Andrew B Kahng, Gabriel Robins, Majid Sarrafzadeh, and CK Wong.  Performance-driven global routing for cell based ics.  In ICCD, volume 91, pages 170–173, 1991.
  * CKR+ [92] Jason Cong, Andrew B Kahng, Gabriel Robins, Majid Sarrafzadeh, and CK Wong.  Provably good algorithms for performance-driven global routing.  Proc. of 5th ISCAS, pages 2240–2243, 1992.
  * CMW+ [94] Boliong Chen, Makoto Matsumoto, Jianfang Wang, Zhongfu Zhang, and Jianxun Zhang.  A short proof of nash-williams’ theorem for the arboricity of a graph.  Graphs and Combinatorics, 10:27–28, 1994.
  * Coh [98] Edith Cohen.  Fast algorithms for constructing t-spanners and paths with stretch t.  SIAM Journal on Computing, 28(1):210–236, 1998.
  * Elk [05] Michael Elkin.  Computing almost shortest paths.  ACM Transactions on Algorithms (TALG), 1(2):283–323, 2005.
  * Erd [65] Paul Erdös.  On some extremal problems in graph theory.  Israel Journal of Mathematics, 3:113–116, 1965.
  * EZ [04] Michael Elkin and Jian Zhang.  Efficient algorithms for constructing (1+, $\varepsilon$, $\beta$)-spanners in the distributed and streaming models.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 160–168, 2004.
  * FKM+ [05] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  Graph distances in the streaming model: the value of space.  In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), volume 5, pages 745–754, 2005.
  * FS [16] Arnold Filtser and Shay Solomon.  The greedy spanner is existentially optimal.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 9–17, 2016.
  * FVWY+ [20] Manuel Fernández V, David P Woodruff, Taisuke Yasuda, et al.  Graph spanners in the message-passing model.  In Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * HHT [23] Bernhard Haeupler, D Ellis Hershkowitz, and Zihan Tan.  Length-constrained expander decompositions: Deeper theory, simpler algorithms.  preprint, 2023.
  * HRG [22] Bernhard Haeupler, Harald Räcke, and Mohsen Ghaffari.  Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality.  In Annual ACM Symposium on Theory of Computing (STOC), pages 1325–1338, 2022.
  * HWZ [20] Bernhard Haeupler, David Wajc, and Goran Zuzic.  Network coding gaps for completion times of multiple unicasts.  In Symposium on Foundations of Computer Science (FOCS), pages 494–505. IEEE, 2020.
  * KV [02] Dejan Kostic and Amin Vahdat.  Latency versus cost optimizations in hierarchical overlay networks.  Technical report, Technical report, Duke University,(CS-2001-04), 2002\.
  * NW [61] C St JA Nash-Williams.  Edge-disjoint spanning trees of finite graphs.  Journal of the London Mathematical Society, 1(1):445–450, 1961\.
  * NW [64] C St JA Nash-Williams.  Decomposition of finite graphs into forests.  Journal of the London Mathematical Society, 1(1):12–12, 1964.
  * [28] David Peleg.  Distributed computing: a locality-sensitive approach.  SIAM, 2000.
  * [29] David Peleg.  Proximity-preserving labeling schemes.  Journal of Graph Theory, 33(3):167–176, 2000.
  * PS [89] David Peleg and Alejandro A Schäffer.  Graph spanners.  Journal of graph theory, 13(1):99–116, 1989.
  * PU [87] David Peleg and Jeffrey D Ullman.  An optimal synchronizer for the hypercube.  In ACM Symposium on Principles of Distributed Computing (PODC), pages 77–85, 1987.
  * RTZ [05] Liam Roditty, Mikkel Thorup, and Uri Zwick.  Deterministic constructions of approximate distance oracles and spanners.  In International Colloquium on Automata, Languages and Programming (ICALP), pages 261–272. Springer, 2005.
  * RZ [04] Liam Roditty and Uri Zwick.  On dynamic shortest paths problems.  In Annual European Symposium on Algorithms (ESA), pages 580–591. Springer, 2004.
  * SCRS [01] F Sibel Salman, Joseph Cheriyan, Ramamoorthi Ravi, and Sairam Subramanian.  Approximating the single-sink link-installation problem in network design.  SIAM Journal on Optimization, 11(3):595–610, 2001.
  * SS [10] Hanan Shpungin and Michael Segal.  Near-optimal multicriteria spanner constructions in wireless ad hoc networks.  IEEE/ACM Transactions on Networking, 18(6):1963–1976, 2010.
  * TZ [01] Mikkel Thorup and Uri Zwick.  Compact routing schemes.  In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 1–10, 2001.
  * TZ [05] Mikkel Thorup and Uri Zwick.  Approximate distance oracles.  Journal of the ACM (JACM), 52(1):1–24, 2005.
  * VRW [04] Pascal Von Rickenbach and Rogert Wattenhofer.  Gathering correlated data in sensor networks.  In Proceedings of the 2004 joint workshop on Foundations of mobile computing, pages 60–66, 2004.
  * VWF+ [03] Jürgen Vogel, Jörg Widmer, Dirk Farin, Martin Mauve, and Wolfgang Effelsberg.  Priority-based distribution trees for application-level multicast.  In Proceedings of the 2nd workshop on Network and system support for games, pages 148–157, 2003.
  * WCT [02] Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang.  Light graphs with small routing cost.  Networks: An International Journal, 39(3):130–138, 2002.